Stack Implementation using Linked List 


Introduction 

In the previous article we have discussed the Stack Implementation using Array. 
As  array is static data type , it's size cannot be changed during the execution of program. Therefore stack implementation using array is not efficient and flexible way to implement stack .  

So , in this article we are going to deeply dive  into the implementation of stack using  Linked List . 

 Why Linked List ?

Even though the array implementation of stack is easy , it has some drawbacks . The size of array needs to declared in advance  .  It is difficult to guess the size of array in advance . This is one of the main drawback of array.

Another drawback of array is that once size of array is , declared it cannot be changed during the execution of program . It dosen't matter whether array is overflowing or is unused . Size remains fixed .

Therefore when resource optimization is concerned , the static implementation becomes inefficient . 
To overcome this problem ,we come come up with another data structure called linked list . 
The main advantage of linked list data structure is  dynamic memory allocation . Memory is allocated at run time , therefore we have freedom to add as many nodes as we want . 


Linked  List Implementation of Stack 

 Here , we have used singly linked list to implement the stack .


Each node in linked list has two fields , data filed and address field . In data field we store our stack data while in address filed we store address of next node . 

Only way to retrieve the elements of linked list is with the help of start pointer  . Hence we assign new notation of type pointer ,Top  to pointer start . 

The underlying  property of stack is that insertion and deletion should occur at only one end . Following this we insert and delete the elements with the help of Top pointer , which holds the address of topmost element .  

If  Top == NULL , then the stack is empty .
If the address field of node is NULL then this node is considered as bottom of stack .  
Operations on Stack
IsEmpty() :
 This function is used to check whether the stack is empty or not . If stack is empty , it returns 1 , otherwise 0 .

Code for IsEmpty() : 
bool  IsEmpty()
{
    if (Top==NULL)

        return true;
  
    else
        return false;
}


Push(int value) :
This function is used to insert the data element at the Top of the stack . It takes one argument , int or float or char type . 

 How does insertion happen in stack  , we will see with the help of an example below .
Suppose , we have to create a stack of four elements . Initially the stack is empty , hence Top = NULL . 

 So , to push 10 , we will call push(10) . It will create a node and insert in the stack  with Top pointing to it (10) . 

To push 20 ,again call push(20) . It will create a new node and insert that node at the top of stack . Top is now pointing to 20 .

Push in Stack
Pushing 10 and 20
Similarly , to push 30 we call push(30). It will create a new node and insert that node at the top of stack .Top now points to 30. 
Push 30
Similarly , to push 40 we call push(40) . It will create a new node and insert that node at the top of stack .Top now points to 40. 

So , stack with four elements looks like this  
Stack after push(40)
One thing to note here is that , we do not have to worry about Stack Full condition as far as there is memory available to allocate . The reason for this is that as linked list is dynamic memory allocation , it can allocate memory at runtime and there is no anything like size in array . 
 
Code for Push(int value) :

void push( int value)
{
    node *newNode = createNode(value); //createNode() is a utility function to create a new node .

    if (Top == NULL)
     {
              Top = newNode;
     }
    else
      {
              newNode->next = Top;
              Top = newNode;
      }
}


 Pop() :
Pop() function deletes the node at the top of stack and returns it to the main. 
It does not take any argument .

To better understand the pop operation , consider an example of stack with four nodes . We can delete the nodes only from Top .

Initially Top is pointing to 40 .
 So ,  when  pop() is called , it deletes 40 . Top now start to point to 30.  
Pop 40
Again , when  pop() is called , it deletes 30 . Top now start to point to 20.
Pop 30
Again , when  pop() is called , it deletes 30 . Top now start to point to 10.
Pop 20
Finally ,when  pop() is called , it deletes 10 . Top now start to point to NULL .
Pop 10
Now the stack is empty and we cannot delete anything . Therefore before deleting element from stack , we have check for IsEmpty() condition .

 Code for Pop() :
int pop()
{
    int x;

    node *delPtr = Top;

    x = Top->data;

    Top =Top->next;

    delete(delPtr);

    return x;
}

  
  # Code for Stack using Linked List 
 Download the code here

#include<iostream>

using namespace std;

struct node
{
    int data;
    node *next;
};
node *Top = NULL;

bool IsEmpty();
void push(int value);
int   pop();
void display();
node *createNode(int value);

int main()
{
    int option,num;

    cout<<"\t\t\t Stack Implementation using Linked List : ";
    do{
        cout<<"-----------------------------------------------------------------------------------\n";
        cout<<"\t\t  1. Push  \n";
        cout<<"\t\t  2. Pop  \n";
        cout<<"\t\t  3. Display  \n";
        cout<<"\t\t  4. Exit  \n";
        cout<<" Enter your choise : ";
        cin>>option;

        switch(option)
        {
            case 1:
                    cout<<"Enter the data to push : ";
                    cin>>num;
                    push(num);
            break;

            case 2:
                    if ( IsEmpty() )

                        cout<<"\t\t\t  Cannot delete the element ! Stack is empty !  \n";

                    else
                    {
                        cout<<"\t\t\t  Poped element is : "<<pop()<<endl;
                    }
            break;

            case 3:
                    if ( IsEmpty() )

                        cout<<"\t\t\t  Oops ! No elements to display ! Stack is Empty   \n";

                    else
                    {
                        cout<<"\t\t\t  Displaying the elements in reverse order : "<<endl;
                        display();
                    }
           break;
        }

    }while(option<=3 && option>=1);
}

bool IsEmpty()
{
    if (Top==NULL)

        return true;
   
    else
        return false;
}

node *createnode(int value)
{
       node *temp = new node;
       temp->data = value;
       temp->next = NULL;
       return temp;
}

void push(int value)
{
       node *newNode = createNode(value);

       if (Top == NULL)
       {
            Top = newNode;
       }
      else
       {
            newNode->next = Top;
            Top = newNode;
       }
}

 int pop()
 {
       int x;
       node *delPtr = Top;
       x = Top->data;
       Top =Top->next;
       delete(delPtr);
       return x;
}

void display()
{
       node *iterator = Top ;
       while(iterator!=NULL)
      {
           cout<<"\t\t"<<iterator->data<<endl;
           iterator = iterator->next;
       }
}

OutPut 

               Stack Implementation using Linked List
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 1
Enter the data to push : 10
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 1
Enter the data to push : 20
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 1
Enter the data to push : 30
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 3
            Displaying the elements in reverse order :
        30
        20
        10
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 2
            Poped element is : 30
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 2
            Poped element is : 20
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 2
            Poped element is : 10
-----------------------------------------------------------------------------------
        1. Push
        2. Pop
        3. Display
        4. Exit
Enter your choise : 2
            Cannot delete the element ! Stack is empty !
-----------------------------------------------------------------------------------
 

Time Complexity : O(1) .

Conclusion :
Linked List is an efficient and flexible option to implement the stack data structure .