This article is a continuation of the Series on Data Structures and carries the discussion on different types of data structures and their implementation. The aim of this series is to provide easy and practical examples that anyone can understand. In our previous tutorial, we have seen how to create a stack using a one-dimensional array. In this article, we are going to see stack implementation using Linked list – Data Structures Part 3.
Prerequisites
We are requesting you to go through the below tutorials, before continuing this.
Introduction
In this stack implementation, data is stored in the form of nodes. You might have heard about nodes if you are familiar with Linked List. In a singly linked list, each node has 2 parts. one is a data part that contains the value of the data and another one is a link(address) that is pointing next node.
As we discussed in the previous article, the stack is following the LIFO (Last-In-First-Out) rule and insertion and deletion are happening on only one end.
Short Introduction of Singly Linked List
The below image explains the concept of a singly linked list.
The above Linked List has 4 Nodes (Node 0, 1, 2, and 3). Here, Node 0 is the head node, and it is pointing to the next node which is Node 1. And Node 1’s address is pointing to Node 2, Node 2’s address is pointing to Node 3. Finally, Node 3’s address is NULL as there is no node to point.
Stack implementation using Linked list
The main advantage of stack implementation using a Linked list over an array is, that the array size is fixed. So, we can’t shrink or increase the size of the stack. But in this method, we can allocate the memory dynamically. So, Increasing or decreasing the size of the stack is possible in the run time.
A stack can be easily implemented using the linked list. The only thing that we need to do is, restrict the addition and deletion of the node from the one end. We can decide to add and delete the node from any end (Beginning or ending). But we prefer to add and delete from only the beginning. Because if you select to add and delete from the end, you need to traverse the linked list to the end every time you add/delete the node. So, it will increase the time complexity.
Operations Performed on Stack
- Push – Inserting the element into the stack
- Pop – Removing the element from the stack
- Display – To display all the stack element
- Peek – Return or print the top element
We will be using the below structure as a node for our code.
// Structure to create a node with data and next (pointer to next node)
struct node
{
int data;
struct node *next;
};
Push Operation
We will have to follow the below steps while adding the new element to the stack.
- First, create a new node using dynamic memory allocation.
struct node* new_node = (struct node*)malloc(sizeof(node));
- Check if the stack is empty or not. if it is empty, set the next pointer of the node to NULL
new_node->next = NULL;
- If the stack has a node already, then add the new element at the beginning, then point the new node to the top element of the stack.
new_node->next = top;
- Update the top pointer.
top = new_node;
The above process has been explained in the below image.
Example code
void push(int data)
{
//Creating a new node
struct node* new_node =(struct node*)malloc(sizeof(node));
if(new_node != NULL)
{
//Update the data
new_node->data = data;
if(top == NULL)
{
new_node->next = NULL;
}
else
{
new_node->next = top;
}
//Update the top
top = new_node;
printf("New element inserted in Stack, Value :%d\n", new_node->data);
}
else
{
printf("Push : Malloc Error\n");
}
}
Pop Operation
In this function, we will be removing or deleting the element from the stack. We will have to follow the below steps while removing the new element from the stack.
- Check whether the stack is underflow or not. If the linked list has no nodes, then the stack is already empty. So, we should not allow the user to delete the node. This condition is called underflow.
if(top == NULL)
{
printf("Stack is Empty : Stack Underflow\n");
}
- Create a temporary node and set it to the top first then create one more variable to have the copy of data of the top element.
struct node* temp = top; int data = top->data;
- Then update the top to point the next node because we are going to delete the temp node and make the top to point the next node.
top = top->next;
- Finally, we can delete the node using the
free().
The above process has been explained in the below image.
Example
int pop()
{
int data = 0;
//Checking whether the stack is underflow or not
if(top == NULL)
{
printf("Stack is Empty : Stack Underflow\n");
}
else
{
struct node* temp = top;
data = top->data;
top = top->next;
free(temp);
printf("The popped value is:%d\n",temp_data);
}
return( data );
}
Display
To print all the elements in the stack, we need to traverse the linked list one by one and print the data. We should not delete any node and should not modify the data.
Example
void display()
{
if(top == NULL)
{
printf("Stack is Empty\n");
}
else
{
struct node *temp = top;
while(temp->next != NULL)
{
printf("%d-->", temp->data);
temp = temp->next;
}
printf("%d--->NULL\n", temp->data);
}
}
Peek
Peek is the option to check the top data without deleting it.
Example
int peek()
{
int data = 0;
if(top == NULL)
{
printf("Stack is Empty\n");
}
else
{
data = top->data;
printf("The top node value is:%d\n",data);
}
return( data );
}
Complete Source Code
Now we can combine the above logic and code. The code is given below.
#include <stdio.h>
#include <stdlib.h>
//Function Declaration
void push(int);
int pop();
int peek();
void display();
//Node structure
struct node
{
int data;
struct node* next;
};
//Stack pointer is empty initially,so assigned to NULL
struct node* top = NULL;
void main()
{
int value;
printf("\n\n***Stack Implementation using singly linked list***\n\n");
while(1)
{
printf("\nEnter the choice:");
scanf("%d",&value);
switch(value)
{
case 1:
printf("Enter the value to push into Stack:");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
printf("Displaying All the stack element:\n");
display();
break;
default:
printf("Please Enter the Correct Choice...\n");
break;
}
}
}
void push(int data)
{
//Creating a new node
struct node* new_node =(struct node*)malloc(sizeof(struct node));
if(new_node != NULL)
{
//Update the data
new_node->data = data;
if(top == NULL)
{
new_node->next = NULL;
}
else
{
new_node->next = top;
}
//Update the top
top = new_node;
printf("New element inserted in Stack, Value :%d\n", new_node->data);
}
else
{
printf("Push : Malloc Error\n");
}
}
int pop()
{
int data = 0;
//Checking whether the stack is underflow or not
if(top == NULL)
{
printf("Stack is Empty : Stack Underflow\n");
}
else
{
struct node* temp = top;
data = top->data;
top = top->next;
free(temp);
printf("The popped value is:%d\n", data);
}
return( data );
}
int peek()
{
int data = 0;
if(top == NULL)
{
printf("Stack is Empty\n");
}
else
{
data = top->data;
printf("The top node value is:%d\n",data);
}
return( data );
}
void display()
{
if(top == NULL)
{
printf("Stack is Empty\n");
}
else
{
struct node *temp = top;
while(temp->next != NULL)
{
printf("%d-->", temp->data);
temp = temp->next;
}
printf("%d-->NULL\n", temp->data);
}
}
Output
***Stack Implementation using singly linked list*** Enter the choice:2 Stack is Empty : Stack Underflow Enter the choice:3 Stack is Empty Enter the choice:1 Enter the value to push into Stack:10 New element inserted in Stack, Value :10 Enter the choice:1 Enter the value to push into Stack:20 New element inserted in Stack, Value :20 Enter the choice:4 Displaying All the stack element: 20-->10-->NULL Enter the choice:2 The popped value is:20 Enter the choice:4 Displaying All the stack element: 10-->NULL Enter the choice:
In our next tutorial, we will discuss Queue data structure in C programming.
You can also read the below topics.
Embedded Software Developer who is passionate about Embedded Systems.
