Unlike arrays, linked lists offer greater flexibility because the stack can expand or contract as needed, avoiding the fixed-size limitations of arrays. Since memory is dynamically allocated for each node, the chances of running into overflow are significantly reduced compared to array-based stacks. In this article, we’ll take a look at the implementation of stack using linked list in C and look at the code for two of the main operations.

Representation of Stack Using Linked List in C

In a linked list-based stack, each stack element is represented by a node, which contains two parts: data (the value stored in the node) and next (a pointer to the next node in the stack). The top pointer refers to the topmost node in the stack. Both push() and pop() operations occur at the top of the linked list, and they run in O(1) time.

The following operations can be performed on a stack:

• push(): Adds an element to the top of the stack. This operation takes O(1) time because each node is inserted at the top (head) of the linked list.

Algorithm: 

Step 1 - Create a new node and allocate memory using malloc().
Step 2 - Check if memory allocation was successful. If not, display "Memory Overflow" and  terminate the function.
Step 3 - Assign the input value to the data field of the new node.
Step 4 - Set the next pointer of the new node to point to the current head of the stack.
Step 5 - Update head to point to the new node, making it the top of the stack.
Step 6 - Print a success message indicating the element has been pushed.

• pop(): Removes the top element from the stack. This also takes O(1) time since the top of the stack always points to the most recently added node.

Algorithm: 

 Step 1 - Check whether the stack is empty (head == NULL).
Step 2 - If it is empty, display "Stack Underflow" and terminate the function.
Step 3 - If the stack is not empty, define a pointer temp and set it to point to head (top of the stack).
Step 4 - Retrieve the value of the top element from temp → data for further use, if needed.
Step 5 - Move the head pointer to the next node (head = head → next).
Step 6 - Free the memory allocated for the temp node.
Step 7 - Print a success message indicating the element has been popped.

• peek(): Returns the top element of the stack without removing it.

Algorithm: 

Step 1 - Check whether the stack is empty (head == NULL).
Step 2 - If it is empty, display "Stack is Empty" and terminate the function.
Step 3 - If the stack is not empty, retrieve the value stored in head → data.
Step 4 - Display the retrieved value as the top element of the stack.

• size(): Returns the number of elements in the stack.

Algorithm: 

Step 1 - Check whether the stack is empty (head == NULL).
Step 2 - If the stack is empty, return size as 0.
Step 3 - If the stack is not empty, initialize a counter variable count to 0.
Step 4 - Define a pointer temp and set it to point to head (top of the stack).
Step 5 - Traverse through the stack using a loop. For each node, increment the count and move temp to the next node (temp = temp → next).
Step 6 - Continue the loop until temp becomes NULL.
Step 7 - Return or display the value of count as the size of the stack.

• isEmpty(): Checks if the stack is empty. It returns true if the stack is empty and false otherwise.

Algorithm: 

Step 1 - Check the value of the head pointer.
Step 2 - If head == NULL, the stack is empty. Return true or display "Stack is Empty".
Step 3 - If head != NULL, the stack contains elements. Return false or display "Stack is Not Empty".

In a stack implemented using a linked list, adding a node is called the push operation. The process of pushing an element onto the stack in a linked list differs from an array-based implementation. Here’s how the push operation works step by step:

Algorithm:

Step 1 - Define a node structure with val and next.
Step 2 - Initialize head = NULL.
Step 3 - Allocate memory for a new node (ptr). If allocation fails, display an error and exit.
Step 4 - Input a value and assign it to ptr → val.
Step 5 - If the stack is empty, set ptr → next = NULL and head = ptr.
Step 6 - Otherwise, set ptr → next = head and update head = ptr.
Step 7 - Print a success message.

Main Function: Call push() to add elements to the stack.

Now let’s take a look at a stack program in C using linked list showing the push operation:

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

// Define the structure for a node
struct node {
    int val;
    struct node* next;
};

// Define the head pointer (top of the stack)
struct node* head = NULL;

// Function to push an element onto the stack
void push() {
    int val;

    // Allocate memory for the new node
    struct node* ptr = (struct node*)malloc(sizeof(struct node));

    // Check if memory allocation failed
    if (ptr == NULL) {
        printf("Unable to push the element. Memory allocation failed.\n");
        return;  // Exit the function if memory allocation fails
    }

    // Prompt user for input
    printf("Enter the value to push: ");
    scanf("%d", &val);

    // Assign the input value to the new node
    ptr->val = val;

    // If the stack is empty, the new node becomes the top node
    if (head == NULL) {
        ptr->next = NULL;  // Set next to NULL as there are no other nodes
        head = ptr;        // Set head to the new node
    } else {
        // Otherwise, insert the new node at the top of the stack
        ptr->next = head;  // Link the new node to the current top
        head = ptr;        // Update head to the new node
    }

    // Print confirmation
    printf("Item %d pushed to stack\n", val);
}

// Main function to test the push operation
int main() {
    push();  // Call push to add an element to the stack
    push();  // Call push again to add another element

    return 0;
}

Output:

Enter the value to push: 10
Item 10 pushed to stack
Enter the value to push: 30
Item 30 pushed to stack


=== Code Execution Successful ===

How it works: 

The code defines a stack using a linked list, where each node holds a value and a pointer to the next node. The push() function allocates memory for a new node, asks the user for a value, and assigns it to the node. If the stack is empty, the new node becomes the top. If not, the new node is added to the top, and the head pointer is updated. After the value is pushed onto the stack, the function prints a confirmation message.

The pop operation removes a node from the top of the stack. This process differs from the array implementation in a linked list implementation of the stack. To pop an element, the following steps are involved:

1. Check for underflow: Underflow happens when an attempt is made to pop from an empty stack. This occurs if the head pointer is NULL, meaning there are no elements in the stack.
2. Update the head pointer: Since elements are removed from the top, we delete the node pointed to by the head. The head pointer is then updated to point to the next node in the list, which removes the topmost element from the stack. The removed node’s memory is freed to prevent memory leaks.

Algorithm: 

Step 1: Create a structure node with val (value) and next (pointer to the next node).

Step 2: Initialize the stack by setting head = NULL.

Step 3: Check if head == NULL to see if the stack is empty.

Step 4: If head is NULL, print "Underflow: Stack is empty" and exit the function.

Step 5: If the stack is not empty, set a pointer ptr to head.

Step 6: Store the value of the top node in a variable item (i.e., item = head->val).

Step 7: Update the head pointer to the next node with head = head->next.

Step 8: Free the memory of the popped node using free(ptr).

Step 9: Print "Item X popped from stack", where X is the value of the popped item.

Main function: Call the pop() function to remove an element from the stack.

Now let’s look at the implementation of stack using linked list in C and pop operation:

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

// Define the structure for a node
struct node {
    int val;
    struct node* next;
};

// Define the head pointer (top of the stack)
struct node* head = NULL;

// Function to pop an element from the stack
void pop() {
    // Check for underflow (empty stack)
    if (head == NULL) {
        printf("Underflow: Stack is empty\n");
        return;  // Exit if the stack is empty
    }

    // Save the value to be popped
    struct node* ptr = head;   // Temporary pointer to the top node
    int item = head->val;      // Get the value of the top node

    // Update the head pointer to the next node
    head = head->next;

    // Free the memory of the popped node
    free(ptr);

    // Print the popped item
    printf("Item %d popped from stack\n", item);
}

// Main function to test pop
int main() {
    // For testing purposes, add a node and then pop
    // Assuming push() function is available to add elements to the stack
    pop();  // Try to pop from an empty stack (underflow)
    return 0;
}

Output:

Underflow: Stack is empty


=== Code Execution Successful ===

How it works: 

The pop() function is meant to remove the top element from the stack. To do this, it first checks if the stack is empty by looking if the head is NULL. If the stack is empty, then it prints an "Underflow" message and stops. If the stack is not empty, it saves the value of the top node. Then, it moves the head to the next node and frees the memory of the old top node. Finally, it prints the value that was removed. This process updates the stack and frees memory properly after each pop.

Displaying the nodes (traversing) means to iterate through the stack or linked list from the head. Then to print each node's value for the user to see. Traversing continues until the end of the list is reached (NULL).

Algorithm: 

Step 1: Create a structure node with val (value) and next (pointer to the next node).

Step 2: Initialize the stack by setting head = NULL.

Step 3: Check if head == NULL to see if the stack is empty.

Step 4: If head is NULL, print "Stack is empty" and exit the function.

Step 5: If the stack is not empty, print "Stack elements:".

Step 6: Set a pointer ptr to head.

Step 7: While ptr is not NULL, print ptr->val.

Step 8: Move ptr to the next node with ptr = ptr->next.

Step 9: Repeat steps 7 and 8 until all elements are printed.

Main function: Call the display() function to display the stack or print "Stack is empty".

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

// Define the structure for a node
struct node {
    int val;
    struct node* next;
};

// Define the head pointer (top of the stack)
struct node* head = NULL;

// Function to display the elements in the stack
void display() {
    if (head == NULL) {  // Check if the stack is empty
        printf("Stack is empty\n");
        return;
    }
    
    struct node* ptr = head;  // Temporary pointer to traverse the stack
    printf("Stack elements: \n");
    while (ptr != NULL) {
        printf("%d\n", ptr->val);  // Print the value of the current node
        ptr = ptr->next;           // Move to the next node
    }
}

// Main function to test the display
int main() {
    display(); // Test display with an empty stack
    return 0;
}

Output:

Stack is empty


=== Code Execution Successful ===

How the code works:

The code creates a stack using a linked list. Each node has a value and a pointer to the next node. The stack is managed by the head pointer, which starts as NULL (empty). The display() function checks if the stack is empty. If it’s empty, it prints "Stack is empty."

If it is not empty, it prints each node's value. The function goes through the stack by following the next pointers, from the first node to the last. The main() function calls display() to show the stack or say if it’s empty.

Here’s how to write a program to implement stack using linked list in C. It shows all the basic stack operations:

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

// Define the structure for a node
struct node {
    int val;
    struct node* next;
};

// Define the head pointer (top of the stack)
struct node* head = NULL;

// Function to push an element onto the stack
void push() {
    int val;
    struct node* ptr = (struct node*)malloc(sizeof(struct node));

    if (ptr == NULL) {
        printf("Unable to push the element. Memory allocation failed.\n");
        return;
    }

    printf("Enter the value to push: ");
    scanf("%d", &val);

    ptr->val = val;
    ptr->next = head;  // Point the new node to the current top node
    head = ptr;        // Update the head to the new node

    printf("Item %d pushed to stack\n", val);
}

// Function to pop an element from the stack
void pop() {
    if (head == NULL) {
        printf("Underflow: Stack is empty\n");
        return;
    }

    struct node* ptr = head;
    int item = head->val;

    head = head->next;  // Move the head pointer to the next node
    free(ptr);          // Free the memory of the popped node

    printf("Item %d popped from stack\n", item);
}

// Function to peek at the top element of the stack
void peek() {
    if (head == NULL) {
        printf("Stack is empty. No top element.\n");
    } else {
        printf("Top element is: %d\n", head->val);
    }
}

// Function to display the stack elements
void display() {
    if (head == NULL) {
        printf("Stack is empty\n");
        return;
    }

    struct node* temp = head;
    printf("Stack elements: ");
    while (temp != NULL) {
        printf("%d ", temp->val);
        temp = temp->next;
    }
    printf("\n");
}

// Function to check if the stack is empty
int isEmpty() {
    return (head == NULL);
}

// Function to return the size of the stack
int size() {
    int count = 0;
    struct node* temp = head;

    while (temp != NULL) {
        count++;
        temp = temp->next;
    }
    return count;
}

// Main function to test the stack operations
int main() {
    int choice;

    while (1) {
        printf("\nStack Operations Menu:\n");
        printf("1. Push\n");
        printf("2. Pop\n");
        printf("3. Peek\n");
        printf("4. Display\n");
        printf("5. Check if Stack is Empty\n");
        printf("6. Get Stack Size\n");
        printf("7. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                push();
                break;
            case 2:
                pop();
                break;
            case 3:
                peek();
                break;
            case 4:
                display();
                break;
            case 5:
                if (isEmpty()) {
                    printf("Stack is empty\n");
                } else {
                    printf("Stack is not empty\n");
                }
                break;
            case 6:
                printf("Stack size: %d\n", size());
                break;
            case 7:
                printf("Exiting...\n");
                exit(0);
            default:
                printf("Invalid choice, please try again\n");
        }
    }

    return 0;
}

Output:

Stack Operations Menu:
1. Push
2. Pop
3. Peek
4. Display
5. Check if Stack is Empty
6. Get Stack Size
7. Exit
Enter your choice: 1
Enter the value to push: 10
Item 10 pushed to stack

Stack Operations Menu:
1. Push
2. Pop
3. Peek
4. Display
5. Check if Stack is Empty
6. Get Stack Size
7. Exit
Enter your choice: 3
Top element is: 10

Stack Operations Menu:
1. Push
2. Pop
3. Peek
4. Display
5. Check if Stack is Empty
6. Get Stack Size
7. Exit
Enter your choice: 2
Item 10 popped from stack

How it works: 

In this program we implement stack operations using a linked list. The push() function adds an element to the top of the stack by creating a new node, assigning it the given value, and updating the head pointer. The pop() function removes the top element, checks for underflow (empty stack), and updates the head pointer. The peek() function displays the top element without removing it, while the display() function shows all elements in the stack. The isEmpty() function checks if the stack is empty, and size() counts the total elements. The program provides an interactive menu for these operations.

Here’s some stack program in C using linked list real-world applications: 

• Undo/Redo Operations: In text editors and graphic software, stacks store the history of actions for undo and redo functionality.
• Expression Evaluation: Used in parsing mathematical expressions (infix to postfix conversion, evaluating postfix expressions).
• Function Call Management: Stacks manage function calls, tracking return addresses and local variables in programming languages.
• Web Browsing History: Browsers use stacks to maintain navigation history for back and forward buttons.
• Memory Management: Stacks are used in managing memory allocation and deallocation in recursive functions.

Learning stacks is crucial for coding students as it enhances problem-solving skills and understanding of key data structures. Stacks are fundamental in managing function calls and memory and handling various real-life applications like expression evaluation and history tracking. Mastering stack operations strengthens algorithmic thinking, enabling students to write efficient and optimised code. It forms the foundation for understanding more advanced concepts and algorithms, making it an essential tool for aspiring programmers. Enroll into the CCBP Academy 4.0 program to learn more and become job-ready.

1. What is a stack using a linked list in C?

In C, a stack employs a linked list, a data structure in which elements are inserted or deleted from the topmost node, known as the peak node. It conforms to the Last In First Out (LIFO) policy using nodes connected by a link.

2. How is the stack represented in the linked list?‍

The stack is represented by a linked list where each node contains a value and a pointer to the next node. The head pointer represents the top of the stack.

3. Is the linked list the same as the stack?

A linked list is a generic data structure that stores the element. A stack is one of the data structures that follow the LIFO principle and is generally implemented using a linked list.

4. What are the advantages of using a linked list to implement a stack?

Using a linked list for a stack allows dynamic memory allocation. It means the stack can grow or shrink as needed, avoiding size limitations and overflow issues typical with arrays.

5. How does stack overflow occur in a linked list implementation?

Stack overflow in a linked list implementation occurs when the system runs out of memory to allocate for new nodes. It's usually due to the excessive pushing of elements without proper memory management.