Stack implementation Using Linked List

In programming, a Stack is a very important data structure that is used to store and manage data efficiently. Imagine a stack like a pile of plates: you can only add or remove the top plate. Similarly, in a stack, elements are added and removed from one end.

A linked list is a basic data structure where each item, called a node, is connected to the next node using pointers, instead of being stored one after another in memory. When we use a linked list to make a stack, its size can vary because each new item is added as a separate node. You don’t need to decide the stack’s size in advance. You can add more items whenever you want, and remove items when they are not needed, which makes it very flexible and efficient with memory.

What is a Stack

Stack is a linear data structure that follows LIFO (Last In First Out) Principle, the last element inserted is the first to be popped out. It means both insertion and deletion operations happen at one end only. In the figure we can see a stack representation in which all numbers are stored as a pile ,one above the other.

LIFO(Last In First Out) Principle

LIFO (Last In, First Out) is a rule that tells us how a stack works. It means the item you add at the end (last) will be the first one to come out. To understand this better, think of a stack of plates in your kitchen. When you put plates one over another, you always place the new plate on the top of the pile. Later, when you need a plate, you don’t take it from the bottom — you simply pick the top plate. So, the plate you placed last will be the first one to be removed. In the same way, in programming, a stack follows this order: the most recently added element will always come out before the older ones.

Operations on Stack

1. Push – Add an element to the top of the stack.
2. Pop – Remove the element from the top of the stack.
3. Peek / Top – Look at the element on the top without removing it.
4. IsEmpty – Check if the stack has no elements.

Example

Suppose we want to store these numbers in a stack: 10, 20, 30

Step 1: Push 10

• Stack: 10
• 10 is at the top because it’s the first element.

Top -> 10

Step 2: Push 20

• Stack:

Top -> 20
       10

• 20 is added on top of 10.

Step 3: Push 30

• Stack:

Top -> 30
       20
       10

• 30 is now the top element.

Step 4: Pop an Element

• Remove the top element (30).
• Stack after pop:

Top -> 20
       10

Step 5: Peek / Top Element

• The top element is now 20.

Step 6: Check if Stack is Empty

• The stack still has elements, so it is not empty.

Why Stack is Implemented with Linked List

We use a linked list to implement a stack because it makes the stack very flexible. Unlike an array, a linked list does not need a fixed size, so you can add as many elements as you want without worrying about running out of space. Each element is stored in a separate node, and nodes are connected using pointers, which allows the stack to easily add or remove items from the top. This makes memory usage efficient and the stack operations like push and pop very fast and simple to manage.

Algorithm for Stack implementation Using Linked List

Push Operation (Insert element in Stack)

Step 1: Start
Begin the push operation by creating a new node.

Step 2: Allocate memory
Use malloc() to create memory for the new node.

Step 3: Check memory
If memory is not available (newNode == NULL), print “Stack Overflow” and stop.

Step 4: Initialize the new node
Set the data part of the new node to the value we want to insert.

Step 5: Link the new node
Set the new node’s next pointer to point to the current top.

Step 6: Update top
Make top point to the new node (the new node becomes the top of the stack).

Step 7: Display success message
Print “Element pushed successfully”.

Step 8: End

Pop Operation (Remove element from Stack)

Step 1: Start
Begin the pop operation.

Step 2: Check if stack is empty
If top == NULL, print “Stack Underflow” and stop.

Step 3: Store top node
Create a temporary pointer temp and set it to top.

Step 4: Update top
Move top to the next node (top = top->next).

Step 5: Free memory
Release the memory of the node stored in temp.

Step 6: Display success message
Print “Element popped successfully”.

Step 7: End

Peek Operation (View top element without removing)

Step 1: Start
Begin the peek operation.

Step 2: Check if stack is empty
If top == NULL, print “Stack is empty” and stop.

Step 3: Access top element
Print the data of the node pointed by top.

Step 4: End

IsEmpty Operation (Check if stack is empty)

Step 1: Start
Begin the IsEmpty operation.

Step 2: Check stack
If top == NULL, return true (stack is empty).
Else, return false (stack is not empty).

Step 3: End

C Code for Stack implementation using Linked List

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

// Define a node
struct Node {
    int data;
    struct Node* next;
};

struct Node* top = NULL; // Global pointer to track top of stack

// Function to push element onto stack
void push(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Stack Overflow (Memory not available)\n");
        return;
    }
    newNode->data = x;
    newNode->next = top;
    top = newNode;
    printf("%d pushed to stack\n", x);
}

// Function to pop element from stack
void pop() {
    if (top == NULL) {
        printf("Stack Underflow (No element to pop)\n");
        return;
    }
    struct Node* temp = top;
    printf("%d popped from stack\n", temp->data);
    top = top->next;
    free(temp);
}

// Function to peek at top element
void peek() {
    if (top == NULL) {
        printf("Stack is empty\n");
    } else {
        printf("Top element is %d\n", top->data);
    }
}

// Function to check if stack is empty
void isEmpty() {
    if (top == NULL) {
        printf("Stack is empty\n");
    } else {
        printf("Stack is not empty\n");
    }
}

// Function to display stack
void display() {
    if (top == NULL) {
        printf("Stack is empty\n");
        return;
    }
    struct Node* temp = top;
    printf("Stack elements are: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    display();

    peek();
    pop();
    display();

    isEmpty();
    pop();
    pop();
    pop(); // Trying to pop from empty stack

    isEmpty();
    return 0;
}

Output

10 pushed to stack
20 pushed to stack
30 pushed to stack
Stack elements are: 30 -> 20 -> 10 -> NULL
Top element is 30
30 popped from stack
Stack elements are: 20 -> 10 -> NULL
Stack is not empty
20 popped from stack
10 popped from stack
Stack Underflow (No element to pop)
Stack is empty

Explanation

struct Node {
    int data;
    struct Node* next;
};

struct Node* top = NULL;

The given code defines the structure of a node for a linked list-based stack and creates an empty stack. Each node has two parts: data, which stores the value of the node, and next, which is a pointer that will point to the next node in the stack. The variable top is a pointer that always keeps track of the element at the top of the stack. It is initially set to NULL, which means the stack is empty and does not contain any nodes yet.

void push(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Stack Overflow (Memory not available)\n");
        return;
    }
    newNode->data = x;
    newNode->next = top;
    top = newNode;
    printf("%d pushed to stack\n", x);
}

In push() function, first a new node is created using malloc() to allocate memory. If memory is not available, it prints “Stack Overflow (Memory not available)” and stops. If memory is successfully allocated, the new node’s data part is set to the value we want to insert, and its next pointer is linked to the current top so that the stack remains connected. After that, the top pointer is updated to this new node, making it the new element at the top of the stack. Finally, a message is displayed to confirm that the element has been pushed into the stack

void pop() {
    if (top == NULL) {
        printf("Stack Underflow (No element to pop)\n");
        return;
    }
    struct Node* temp = top;
    printf("%d popped from stack\n", temp->data);
    top = top->next;
    free(temp);
}

The pop() function removes the top element from the stack. First, it checks if the stack is empty by seeing if top == NULL. If it is empty, it prints “Stack Underflow (No element to pop)” and returns, because there’s nothing to remove. If the stack has elements, a temporary pointer temp is created to store the current top node. It then prints the value being popped, updates the top to point to the next node, and finally frees the memory of the old top node. This ensures the element is properly removed from the stack.

void peek() {
    if (top == NULL) {
        printf("Stack is empty\n");
    } else {
        printf("Top element is %d\n", top->data);
    }
}

The peek() function shows the value of the top element in the stack without removing it. It first checks if the stack is empty by seeing if top == NULL. If the stack is empty, it prints “Stack is empty”. Otherwise, it displays the value stored in the top node using top->data. This way, you can see what element is currently at the top of the stack.

void isEmpty() {
    if (top == NULL) {
        printf("Stack is empty\n");
    } else {
        printf("Stack is not empty\n");
    }
}

The isEmpty() function checks whether the stack has any elements or not. It looks at the top pointer. If top == NULL, it means there are no elements, so it prints “Stack is empty”. If top is not NULL, it means the stack has at least one element, so it prints “Stack is not empty”.

void display() {
    if (top == NULL) {
        printf("Stack is empty\n");
        return;
    }
    struct Node* temp = top;
    printf("Stack elements are: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

The display() function shows all elements of the stack from top to bottom. First, it checks if the stack is empty by seeing if top == NULL. If the stack is empty, it prints “Stack is empty” and stops. If not, it uses a temporary pointer temp starting from top and moves through the linked list using a while loop. At each step, it prints the value of the current node followed by an arrow (->). When the end of the stack is reached, it prints NULL to show the end of the list.

int main() {
    push(10);
    push(20);
    push(30);
    display();

    peek();
    pop();
    display();

    isEmpty();
    pop();
    pop();
    pop(); // Trying to pop from empty stack

    isEmpty();
    return 0;
}

The main() function demonstrates how all the stack operations work. First, three elements (10, 20, and 30) are pushed into the stack. Then display() is called to print the stack elements. After that, peek() shows the current top element. The pop() function is then used to remove the top element, and display() again shows the updated stack. The program checks if the stack is empty using isEmpty(). After that, more pop() operations are done until the stack becomes empty, including one extra pop to test the underflow condition. Finally, isEmpty() is called again to confirm the stack is empty.

Time Complexity

Operation	Best Case	Average Case	Worst Case
Push	O(1)	O(1)	O(1)
Pop	O(1)	O(1)	O(1)
Peek	O(1)	O(1)	O(1)
IsEmpty	O(1)	O(1)	O(1)
Display	O(1)	O(n)	O(n)

Space Complexity

Operation	Best Case	Average Case	Worst Case
Push	O(1) / O(n total)	O(1) / O(n total)	O(1) / O(n total)
Pop	O(1)	O(1)	O(1)
Peek	O(1)	O(1)	O(1)
IsEmpty	O(1)	O(1)	O(1)
Display	O(1)	O(1)	O(1)

Application of Stack

1. Expression Evaluation – Used to evaluate arithmetic expressions like infix, postfix, and prefix.
2. Expression Conversion – Convert expressions from infix to postfix/prefix or vice versa.
3. Undo/Redo Operations – Many applications like MS Word or Photoshop use stacks to undo or redo actions.
4. Function Call Management – Recursion and function calls are managed using a stack in programming languages.
5. Browser Back/Forward – Web browsers use stacks to store visited pages for back and forward navigation.
6. Syntax Parsing – Compilers use stacks to check for balanced parentheses, braces, or brackets.
7. Backtracking Algorithms – Problems like maze solving, puzzle solving, or pathfinding use stacks.
8. Memory Management – Stack memory is used for local variables and function call storage in programs.
9. Undo in Text Editors – Keeps track of previous actions to revert changes.
10. Stack in Algorithms – Many algorithms like DFS (Depth-First Search) in graphs use stack for traversal.