Doubly Linked List using Stack in c++

Question

Just started learning/relearning data structures for the semester exams. Most of the examples found online are too cluttered or bloated.

For myself, I implemented it from theory I learned.

It works.

I want to know if there are any mistake that I have done, anything that can be improved .. .

Thanks for your time :)

#include "iostream"
using namespace std;

struct Node{

    struct Node* prev;
    int data;
    struct Node* next;

};

Node* top = NULL;

bool isempty(){
    return  top->prev == NULL;
}

void push(int data){

    struct Node* newnode;
    newnode = new Node();

    if(!newnode){
        cout << "Heap Overflow" << endl;
    }

    newnode->prev = top;
    newnode->data = data;  
    newnode->next = NULL;

    top = newnode;
}

void pop(){

    if(isempty()){
        cout << "Stack Underflow";
        exit(1);
    }

    struct Node* tmp;
    tmp = new Node();

    tmp->next = NULL;
    tmp->data = top->prev->data;
    tmp->prev = top->prev->prev;

    free(top);
    top = tmp;

}

void display(){

    struct Node* itr;
    itr = top;

    cout << itr->data << " ";
    while(itr->prev != NULL){
        cout << itr->prev->data << " ";
        itr = itr->prev;
    }
    cout << endl;
}

int main(){

    push(10);
    push(20);
    push(30);
    push(40);
    push(50);

    pop();
    display();
    pop();
    display();
    pop();
    display();
    pop();
    display();
    pop();

    return 0;
}

Answer 1

Welcome to Code Review!

Bugs

For every node you insert, next is null.

Encapsulation

Your code is written almost exclusively using C features. First things first, instead of using a single global variable, use a class to encapsulate the data structure.

class Stack {
public:
    Stack() = default;
    Stack(const Stack&) = delete;
    Stack& operator=(const Stack&) = delete;
    ~Stack();

    void push(int data);
    void pop();
    void display() const;
    bool empty() const { return top == nullptr; }
private:
    struct Node {
        int data;
        Node* prev;
        Node* next;
    };
    Node* top = nullptr;
};

The way the function works is exactly the same. A destructor should be provided to systematically handle memory deallocation:

Stack::~Stack()
{
    while (!empty()) {
        pop();
    }
}

Now Stack can be used like a normal C++ container:

int main()
{
    Stack stack1;
    stack1.push(3);
    stack1.push(1);
    stack1.push(4);
    stack1.display();
    stack1.pop();
    stack1.display();

    Stack stack2;
    // stack2 is a stack independent from stack1
} // the existing nodes are automatically freed when the main function returns

Miscellaneous

#include "..." is for your own headers. For standard headers, use #include <iostream>.

using namespace std; at global level is considered bad practice and should be avoided because it defeats the purpose of namespaces and introduce name clashes. You will have trouble using identifiers as common as size or count. See Why is using namespace std; considered bad practice?

A class can be referred to directly with its name. You don't need to add struct. So instead of struct Node*, just say Node*.

Instead of NULL, use nullptr for null pointer constants.

It's more common to write functions in this way:

bool isempty()
{
    // ...
}

Instead of declaring a variable uninitialized and then assigning to it immediately, use initialization.

The push and pop functions are way too convoluted. Remember you are implementing a stack, not a complete doubly linked list. Aggregate initialization with new can be used to simplify the code:

void Stack::push(int value)
{
    top = new Node{value, top, nullptr};
    if (auto old = top->prev) {
        old->next = top;
    }
}

void Stack::pop()
{
    if (empty()) {
        throw Stack_underflow{};
    }
    delete std::exchange(top, top->prev);
}

Note that heap overflow is not something you need to worry about because new already throws an appropriate exception on allocation failure. Also, do not free memory allocated by new with free. This is undefined behavior. Use new with delete instead.

When an error happens, throw an exception instead of printing a message and then exiting or even continuing execution. There is not always an open stdout file, and if it exists, that's now how everyone wants error to be handled. Throwing an exception allows the user to handle it in the convenient way.

The while loop in the display function should have been simplified with a for loop:

for (Node* itr = top; itr; itr = itr->prev) {
    std::cout << itr->data << '\n';
}

Note that std::endl should be avoided when you don't need the flushing semantics. Unnecessary flushing can cause performance degradation. See std::endl vs \n.

return 0; can be omitted in a main function.

Refined version

Putting everything together:

#include <iostream>
#include <stdexcept>
#include <utility>

struct Stack_underflow :std::exception {};

class Stack {
public:
    Stack() = default;
    Stack(const Stack&) = delete;
    Stack& operator=(const Stack&) = delete;
    ~Stack();

    void push(int value);
    void pop();
    void display() const;
    bool empty() const { return top == nullptr; }
private:
    struct Node {
        int data;
        Node* prev;
        Node* next;
    };
    Node* top = nullptr;
};

Stack::~Stack()
{
    while (!empty()) {
        pop();
    }
}

void Stack::push(int value)
{
    top = new Node{value, top, nullptr};
    if (auto old = top->prev) {
        old->next = top;
    }
}

void Stack::pop()
{
    if (empty()) {
        throw Stack_underflow{};
    }
    delete std::exchange(top, top->prev);
}

void Stack::display() const
{
    for (auto it = top; it; it = it->prev) {
        std::cout << it->data << ' ';
    }
    std::cout << '\n';
}

int main()
{
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    stack.pop();
    stack.display();
    stack.pop();
    stack.display();
}

Output:

4 3 2 1 
3 2 1 

(live demo)