Implement a Stack using a 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();
}

This code adds elements to the head node, and also removes elements from the head node.

Source: An Algorithm a Day, http://analgorithmaday.blogspot.com/2011/06/implement-stack-using-linked-list.html
 This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.