Stack implementation using Linked list – Data Structures Part 3

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.

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.

Linux Device Driver TutorialsC Programming Tutorials
FreeRTOS TutorialsNuttX RTOS Tutorials
RTX RTOS TutorialsInterrupts Basics
I2C Protocol – Part 1 (Basics)I2C Protocol – Part 2 (Advanced Topics)
STM32 TutorialsLPC2148 (ARM7) Tutorials
PIC16F877A Tutorials8051 Tutorials
Unit Testing in C TutorialsESP32-IDF Tutorials
Raspberry Pi TutorialsEmbedded Interview Topics
Reset Sequence in ARM Cortex-M4BLE Basics
VIC and NVIC in ARMSPI – Serial Peripheral Interface Protocol
Bootloader TutorialsRaspberry PI Pico Tutorials
Zephyr RTOS Tutorials - STM32Zephyr RTOS Tutorials - ESP32
VHDL TutorialsUDS Protocol Tutorials
Product Reviews
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments