Implement a Stack using a Linked List

We've seen several code implementations thus far, but it is worth looking at another approach, since there are many possible approaches. Some are better than others, depending on the application. Do not let yourself become set on one specific way of doing things.

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
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Last modified: Monday, November 16, 2020, 5:46 PM