Representation of a Stack as a Linked List | C Program

What is Linked representation of Stack a in Data Structure

First, we have to understand what a linked list is, to understand linked list representation of a stack. A Linked List is a Data Structure which consists of two parts:

  • The data/value part.
  • The pointer which gives the location of the next node in the list.

Stack can also be represented by using a linked list. We know that in the case of arrays we face a limitation , i.e , array is a data structure of limited size. Hence before using an array to represent a stack we will have to consider an enough amount of space to suffice the memory required by the stack.

However, a Linked List is a much more flexible data structure. Both the push and pop operations can be performed on either ends.. But We prefer performing the Push and pop operation at the beginning.

 The Stack operations occur in constant time. But if we perform the push and pop operations at the end of the linked list it takes time O(n).

But performing the operations at the beginning occurs in constant time. Let us understand this with the help of an example.

Let us consider a linked list as shown here.

In the given data we can see that we have-

  • Head = 200.
  • Top = 33.

Push / Pop At the end Of a Linked List

Consider the Linked List as shown above. Now if we want to push/pop a node at the end, we have to traverse all the n number of nodes, until we reach the end of the linked list.

We traverse the whole list from the beginning to the end.

  • Now if we want to insert a node at the end of the linked list, we traverse from the first node to the second node to the last node.
  • We find the end of the list where the node points to the null and the node to be inserted is as shown here.
  • The new node is pushed at the end of the list.
  • The second last node , i.e, 08 now points to the location of the last node.
  • The newly inserted node at the end now points to null.

Push / Pop operation at the beginning of the Linked List

Pushing a new node at the beginning of a linked list takes place in constant time. When inserting the new node the number of traversals that occur is equal to 1. So it  is much faster than the previous method of insertion

The time complexity of inserting a new node at the beginning of the linked list is O(1).

Let us consider the previous example only. We are given a Linked List as follows:

  •  A new node to be inserted to the Linked List is shown here.
  • The new node 40 is to be inserted at the beginning of the list.
  •  The new node is inserted at the beginning where we have just a single traversal after spotting the head of the Linked List.
  • The value of head changes from 200 to 100.
  • The pointer of the new node stores the address of the next node.
  • The final linked list is shown here.

Implementation of a Stack using a Linked List

#include <stdio.h>  
#include <stdlib.h>

void Push(); /*to insert the element*/

void pop(); /*to delete the element*/

void display(); /*to display the elements in a stack*/

struct n
{
int element;
struct n *nxt;
};
struct n *hd;

void main ()
{
int option=0;
while(option != 4)
{
printf("\nSelect from the following options\n1.Push\n2.Pop\n3.Show\n4.Exit \nEnter one of your choices:");
scanf("%d",&option);
switch(option)
{
case 1:
{
Push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exit");
break;
}
default:
{
printf("\nKindly enter a valid option\n");
}
};
}
}
void Push ()
{
int element;
struct n *ptr = (struct n*)malloc(sizeof(struct n));
if(ptr == NULL)
{
printf("Stack full. Operation failed");
}
else
{
printf("Enter the element you want to insert: ");
scanf("%d",&element);
if(hd==NULL)
{
ptr->element = element;
ptr -> nxt = NULL;
hd=ptr;
}
else
{
ptr->element = element;
ptr->nxt = hd;
hd=ptr;

}
printf("Element is inserted");

}
}

void pop()
{
int num;
struct n *ptr;
if (hd == NULL)
{
printf("Not enough elements. Underflow!");
}
else
{
num = hd->element;
ptr = hd;
hd = hd->nxt;
free(ptr);
printf("Element deleted: %d",num);

}
}
void display()
{
int i;
struct n *ptr;
ptr=hd;
if(ptr == NULL)
{
printf("The stack is empty\n");
}
else
{
printf("The stack elements are as follows: \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->element);
ptr = ptr->nxt;
}
}
}