Implement a Stack using Linked List

 

Question

  You need to implement a stack using singly linked list so that POP and PUSH takes O(1) similar performance of an array. How would you do that?

Concept

  We know about LIFO in a stack. We have to just maintain the element added to the linked list at the top. Then you will get a PUSH at the top with O(1) and POP at the top with O(1).

Code

class StackList 

{

    struct ListNode {

        int data;

        ListNode* next;

    };

    ListNode *head;

public:

    StackList() : head(NULL) {}

    void push(int data);

    int pop();

};

void StackList::push(int data)

{

    ListNode* n = new ListNode;

    n->data = data;

    n->next = head;

    head = n;

}

int StackList::pop()

{

    if(head == NULL)

        return -1;

    int tdata = head->data;

    ListNode* next = head->next;

    free(head);

    head = next;

    return tdata;

}

void main()

{

    StackList obj;

    obj.push(5);

    obj.push(3);

    obj.push(2);

    obj.push(10);

    cout<<obj.pop();

}

• Add elements to the head node
• Remove elements also from the head node