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.

Key Takeaways So Far

• Push operation efficiently adds elements to the stack dynamically using linked list nodes.
• Pop operation safely removes top elements while preventing memory leaks and underflow errors.
• Quick checks like isEmpty and peek are essential for safe stack operations.

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.

Below is a full example of a stack implementation in C using a singly linked list. This program demonstrates all the essential stack operations—push, pop, peek, display, isEmpty, and size—using dynamic memory allocation. For demonstration purposes, the stack is limited to a maximum size of 5 elements using #define size 5.

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

#define size 5

// Define the node structure for the singly linked list
struct node {
    int data;
    struct node *next;
};

// Head pointer representing the top of the stack
struct node* head = NULL;
int current_size = 0;

// Function to push an element onto the stack
void push() {
    if (current_size == size) {
        printf("Stack Overflow: Maximum size reached (%d)\n", size);
        return;
    }

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

    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }

    newNode->data = val;
    newNode->next = head;
    head = newNode;
    current_size++;

    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* temp = head;
    int popped = head->data;
    head = head->next;
    free(temp);
    current_size--;

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

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

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

    struct node* temp = head;
    printf("Stack elements: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        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 stack_size() {
    return current_size;
}

// Main function to test 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", stack_size());
                break;
            case 7:
                printf("Exiting...\n");
                exit(0);
            default:
                printf("Invalid choice, please try again\n");
        }
    }

    return 0;
}

How It Works:

• The program defines a struct node for each stack element, with fields for data and a pointer to the next node.
• The head pointer always points to the top of the stack.
• The stack size is managed using current_size and is limited by #define size 5.
• All stack operations (push, pop, peek, display, isEmpty, stack_size) are handled via dedicated functions.
• The main function provides a menu-driven interface for user interaction.

Key Takeaways So Far 

• Display operation traverses the stack efficiently to show all elements in order.
• Peek, isEmpty, and size functions provide quick information about stack status.
• Menu-driven programs improve understanding and testing of stack operations dynamically.

Below are typical outputs you might encounter when running the stack program. These samples show how stack operations affect the linked list and how the program responds to different scenarios.

Sample Run

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: 25
Item 25 pushed to stack

Enter your choice: 1
Enter the value to push: 40
Item 40 pushed to stack

Enter your choice: 4
Stack elements: 40 25

Enter your choice: 2
Number popped = 40
// free(temp) releases memory for the popped node
// top-- decreases the stack size

Enter your choice: 4
Stack elements: 25

Enter your choice: 2
Number popped = 25
// free(temp) releases memory
// top-- decreases stack size

Enter your choice: 2
Stack is empty

Enter your choice: 6
Stack size: 0

Enter your choice: 5
Stack is empty

Explanation

• When a value is popped, the program prints number popped = %d using printf("number popped = %d",start->data) before updating start=start->next and freeing the removed node with free(temp). The top-- operation (if a size variable is used) decrements the count.
• If the stack is empty (start==NULL), the program prints stack is empty.
• The size() function call displays the current number of elements.
• If getch() is used in your program (as seen in some competitor examples), it pauses the output after each operation, allowing users to see messages before proceeding.

Notes

• These outputs help users confirm that their stack implementation correctly manages memory, updates pointers, and handles edge cases (like popping from an empty stack).
• If your program uses getch() to pause after messages (as seen in some competitor examples), you may include prompts like "Press any key to continue…" after each operation.

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.

Bottom Line: Stacks are essential in recursion, expression evaluation, undo features, and efficient function call management.

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.

Why does it matter?

Understanding stacks implemented with linked lists is crucial because it combines dynamic memory management with core data structure concepts. This knowledge helps learners write efficient, flexible programs and prepares them for advanced topics like recursion, expression evaluation, and algorithm optimization.

Practical advice for learners

• Practice​‍​‌‍​‍‌​‍​‌‍​‍‌ the implementation of stack operations by both arrays and linked lists.
• Use your stack in real-world situations such as undo features or expression evaluation.
• Concentrate on the completion of edge cases, for example, stack underflow and overflow.
• Illustrate the stack operations one by one to deepen the understanding of the concept.
• In time, you can merge stacks with other data structures for complicated ​‍​‌‍​‍‌​‍​‌‍​‍‌applications.

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.