Saturday, 4 June 2011

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