Stack Using Linked List in C

A stack data structure operates on the LIFO (Last In, First Out) principle. Elements are added and removed from the top, making it perfect for scenarios like undo operations in applications, where you need quick access to the most recently added item.

For beginners, managing a stack with a linked list algorithm can be tricky, especially when it comes to implementing operations like push and pop effectively.

In this guide, you’ll learn how to implement a stack using a linked list in C with examples and how to handle the operations seamlessly. Let’s dive into the details!

Boost your C programming skills with our Software Development courses— take the next step in your learning journey!

Implementing a Stack Using Linked List in C

A stack is commonly used in applications such as text editors' undo functionality, web browser history, and expression evaluation. This section will focus on a practical example of implementing undo functionality using a stack.

Imagine you are developing a text editor that supports the undo feature. The action is stored in a stack every time the user types something. When the user presses undo, the most recent action is popped from the stack, allowing the editor to revert to the previous state.

Pressing "undo" after the stack is empty should be handled gracefully by displaying a message or preventing further undo actions.

Let’s break down the steps involved:

1. Initialize the Stack:

• Define the stack using a linked list. Each node stores an action (text), and the top pointer keeps track of the most recent action.

2. Push Operation (Add Action to Stack):

• Allocate memory for a new node.
• Copy the user input (text) into the new node.
• Link the new node to the top of the stack.
• Update the top pointer to point to the new node.

3. Pop Operation (Undo Action):

• Check if the stack is empty (if top is NULL).
• If not empty, print the data of the top node (the action to undo).
• Move the top pointer to the next node.
• Free the memory of the removed node.

4. Handle Empty Stack:

• If the stack is empty and a pop is attempted, display an appropriate message like "No actions to undo".

5. Testing:

• Push multiple actions to the stack (simulate user input).
• Pop actions one by one to undo them in reverse order.
• Ensure that empty stack handling works by preventing further undo actions after the stack is empty.

Let’s walk through this undo functionality implementation using the stack using linked list algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Define a node structure for the stack
struct Node {
    char data[100];     // Store text entered by the user (up to 100 characters)
    struct Node* next;  // Points to the next node in the stack
};
// Define the top of the stack (initially NULL)
struct Node* top = NULL;
// Push operation to insert an element (text) at the top of the stack
void push(char text[]) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory for the new node
    if (newNode == NULL) {  // Check for memory allocation failure
        printf("Memory overflow\n");
        return;
    }
    strcpy(newNode->data, text);  // Copy the text into the new node's data field
    newNode->next = top;          // Link the new node to the current top node
    top = newNode;                // Move the top pointer to the new node
    printf("Text added: %s\n", text);  // Print the added text
}
// Pop operation to remove the top element (undo action)
void pop() {
    if (top == NULL) {  // Check if the stack is empty (no actions to undo)
        printf("No actions to undo\n");
        return;
    }
    struct Node* temp = top;  // Temporarily store the top node
    printf("Undo: %s\n", temp->data);  // Print the action to be undone
    top = top->next;  // Move the top pointer to the next node
    free(temp);       // Free the memory of the old top node
}
int main() {
    push("Typed: Hello, World!");  // Simulate typing text
    push("Typed: How are you?");   // Simulate typing more text
    push("Typed: Goodbye!");       // Another text input
    pop();  // Undo the last action (Goodbye!)
    pop();  // Undo the second last action (How are you?)
    pop();  // Undo the first action (Hello, World!)
    return 0;
}

Output:

Text added: Typed: Hello, World!
Text added: Typed: How are you?
Text added: Typed: Goodbye!
Undo: Typed: Goodbye!
Undo: Typed: How are you?
Undo: Typed: Hello, World!

Explanation:

1. Push Operation (Adding Text):

• The push function is used to add an action to the stack. Every time the user types something, the input (text) is stored in a new node, which is linked to the previous one (if any).
• The text is copied into the new node’s data field using strcpy, and the top pointer is updated to point to this new node, making it the new top of the stack.

2. Pop Operation (Undoing Action):

• The pop function removes the most recent action from the stack. When the user presses undo, the top action (text) is printed and then removed from the stack.
• The top pointer is updated to point to the next node in the stack (the previous action), and the memory for the removed node is freed using free().

3. Handling Empty Stack:

• The pop operation first checks if the stack is empty by checking if top == NULL. If it is, it prints "No actions to undo" and returns without making any changes.

Key Takeaways:

• Undo Functionality: Every action (text input) is pushed onto the stack, and when the user presses undo, the most recent action is popped.
• Memory Management: Each time a new action is added to the stack, memory is dynamically allocated using malloc(). When the action is undone, memory is freed with free(), preventing memory leaks.
• Linked List Structure: The stack is implemented using a linked list, which means it is not fixed in size and can grow dynamically as the user performs more actions.

Also Read: What are Data Structures in C & How to Use Them?

Stacks are widely used in many applications, and this stack, which uses a linked list algorithm, will help you efficiently tackle problems like undo functionality.

Next, let’s look at the key operations you can perform on stack.

Operations Performed on a Stack

Now that you understand the knows and hows, let's dive deeper and explore the essential operations that can be performed on stack.

The two main operations on a stack are push and pop.

Push Operation

The push operation inserts an element at the top of the stack. When using a stack using a linked list in C, for example, you create a new node with the element and link it to the top of the stack.

Let’s break down the steps involved:

1. Create a New Node:

When you push an element onto the stack, memory is allocated for a new node, which will hold the value.

2. Link the New Node:

The new node’s next pointer is set to point to the current top node, linking the new node to the stack.

3. Update the Top Pointer:

The top pointer is updated to point to the new node, making it the new top of the stack.

As shown in the diagram above, each new element gets added to the front of the stack, becoming the top element.

Let's implement the push function for a stack implemented using a linked list:

#include <stdio.h>
#include <stdlib.h>
// Define a node structure for the stack
struct Node {
    int data;          // Stores the data of the node
    struct Node* next; // Pointer to the next node in the stack
};
// Define the top of the stack
struct Node* top = NULL;
// Push operation to insert an element at the top
void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory for the new node
    if (newNode == NULL) {    // Check for memory allocation failure
        printf("Memory overflow\n");
        return;
    }
    newNode->data = value;   // Set the node's data
    newNode->next = top;      // Link the new node to the current top node
    top = newNode;            // Move the top pointer to the new node
    printf("Pushed %d to stack\n", value);
}
int main() {
    push(15);  // Push 15 to the stack
    push(87);  // Push 87 to the stack
    push(24);  // Push 24 to the stack
    return 0;
}

Output:

Pushed 10 to stack
Pushed 20 to stack
Pushed 30 to stack

Explanation:

• newNode creation: We first allocate memory for a new node using malloc.
• Data assignment: The data field of the node is set to the value passed in the push function.
• Linking: The next pointer of the new node is linked to the current top node (the node before the new one).
• Updating top: The top pointer is updated to the new node, making it the new top of the stack.

Pop Operation

The pop operation is used to remove and return the top element of the stack.

Let’s break down the steps involved:

1. Check for Underflow:

First, check if the stack is empty. If it is, print a message indicating no elements are available to pop.

2. Access the Top Node:

Temporarily store the top node to access its data and prepare for removal.

3. Update the Top Pointer:

Move the top pointer to the next node, effectively removing the current top node from the stack.

4. Free the Memory:

After updating the pointer, free the memory occupied by the removed node.

The diagram illustrates how each pop operation removes the topmost node and moves the top pointer to the next node, reducing the stack by one element.

Let's write the pop function to remove the top element:

#include <stdio.h>
#include <stdlib.h>
// Define a node structure for the stack
struct Node {
    int data;          // Stores the data of the node
    struct Node* next; // Pointer to the next node in the stack
};
// Define the top of the stack
struct Node* top = NULL;
// Pop operation to remove the top element from the stack
int pop() {
    if (top == NULL) {  // Check if the stack is empty
        printf("Stack underflow\n");
        return -1;  // Return a special value to indicate that the stack is empty
    }    
    struct Node* temp = top;   // Temporarily store the top node
    int poppedValue = temp->data;  // Save the data of the top node
    top = top->next;  // Move the top pointer to the next node
    free(temp);       // Free the memory of the old top node    
    return poppedValue;  // Return the data of the popped node
}
int main() {
    push(15);  // Push 15 to the stack
    push(87);  // Push 87 to the stack
    push(24);  // Push 24 to the stack    
    printf("Popped %d from stack\n", pop());  // Pop the top element (24)
    printf("Popped %d from stack\n", pop());  // Pop the new top element (87)
    printf("Popped %d from stack\n", pop());  // Pop the new top element (15)    
    return 0;
}

Output:

Pushed 15 to stack
Pushed 87 to stack
Pushed 24 to stack
Popped 24 from stack
Popped 87 from stack
Popped 15 from stack

Explanation:

1. Pop Operation:

• First Pop (Popped 24): The top node containing 24 is removed from the stack. The stack now has 87 and 15, with 87 being the new top.
• Second Pop (Popped 87): The new top node containing 87 is removed, leaving 15 as the top.
• Third Pop (Popped 15): The top node containing 15 is removed, leaving the stack empty.

2. Underflow Check: Each time we pop, the function checks if the stack is empty (top == NULL). If it is, it prints "Stack underflow" and returns -1.

3. Memory Cleanup: After popping, the memory of the removed node is freed using free(temp), ensuring there are no memory leaks.

Also Read: What Are Storage Classes in C?

Peek Operation

In addition to push and pop, you often need to peek at the top element without removing it from the stack.

This operation is often used when you're interested in the current state of the stack, but not necessarily in modifying it.

Let’s look at the steps for Implementing the Peek Operation:

1. Check if the Stack is Empty:

Before peeking, you need to ensure that the stack isn’t empty. If the stack is empty, attempting to peek will result in an error, so the function should handle this case gracefully.

2. Access the Top Element:

If the stack is not empty, the top element can be accessed using the top pointer. You can directly retrieve the data stored in the top node.

3. Return the Value:

Once you access the top element, return it without removing it from the stack.

Let’s walk through how the peek operation can be implemented:

// Peek operation to view the top element of the stack without removing it
int peek() {
    if (top == NULL) {  // Check if the stack is empty
        printf("Stack is empty\n");
        return -1;
    }
    return top->data;  // Return the data of the top node without modifying the stack
}

Explanation:

The peek operation simply checks if the stack is empty and returns the data of the top node without removing it, allowing you to view the top element.

IsEmpty Operation

The IsEmpty operation is used to check if the stack is empty. This operation is crucial because you want to prevent performing operations like pop or peek on an empty stack, which could lead to errors.

In a stack using a linked list in C, the stack is considered empty when the top pointer is NULL, indicating that there are no elements in the stack.

Let’s start by writing the IsEmpty function to check whether the stack is empty:

#include <stdio.h>
#include <stdlib.h>
// Define a node structure for the stack
struct Node {
    int data;          // Stores the data of the node
    struct Node* next; // Pointer to the next node in the stack
};
// Define the top of the stack
struct Node* top = NULL;
// IsEmpty operation to check if the stack is empty
int isEmpty() {
    return top == NULL; // Return true if top is NULL, meaning the stack is empty
}
int main() {
    printf("Is stack empty? %d\n", isEmpty()); // Check if the stack is empty
    // Pushing elements to the stack
    push(10);
    push(20);
    printf("Is stack empty? %d\n", isEmpty()); // Check if the stack is empty again
    return 0;
}

Output:

Is stack empty? 1
Pushed 10 to stack
Pushed 20 to stack
Is stack empty? 0

Explanation:

• isEmpty Function: The isEmpty function checks if the cc. If top is NULL, it means there are no nodes in the stack, and the function returns 1 (true). If there are nodes in the stack, it returns 0 (false).
• Checking Stack Status: Initially, since no elements are in the stack, the function returns 1. After pushing elements, the stack is no longer empty, and the function returns 0.

IsFull Operation

In a stack using linked list in C, the IsFull operation is usually unnecessary because the stack's size is dynamic, and a linked list does not have a predefined size limit.

However, in an array-based stack, you may need to check whether the stack has reached its maximum size, in which case it is full.

For educational purposes, let’s look at how IsFull would be implemented for an array-based stack:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5 // Define the maximum size of the stack
// Define a node structure for the stack
struct Node {
    int data;          // Stores the data of the node
    struct Node* next; // Pointer to the next node in the stack
};
// Define the top of the stack
struct Node* top = NULL;
// IsFull operation for an array-based stack (for reference)
int isFull(int size) {
    return size == MAX_SIZE; // Return true if the stack has reached the maximum size
}
int main() {
    int size = 0;
    // Checking if the stack is full
    printf("Is stack full? %d\n", isFull(size));
    // Simulating stack operations
    size++;
    printf("Is stack full? %d\n", isFull(size));
    return 0;
}

Output:

Is stack full? 0
Is stack full? 0

Explanation:

• isFull Function: The isFull function checks if the stack has reached the maximum allowed size. If the size of the stack is equal to MAX_SIZE, the function returns 1 (true), indicating the stack is full. Otherwise, it returns 0 (false).
• Simulated Stack: In this example, we simulate adding one element to the stack. Initially, the stack is not full, so the function returns 0.

Keep exploring different use cases and scenarios to master stack behavior, whether for managing function calls, expression evaluation, or dynamic data.

How Well Do You Know Stack Using Linked List in C? 10 MCQs

Ready to put your knowledge of stack operations to the test? This quiz will help you assess your understanding of stacks implemented using linked lists in C programming.

1. What is the primary advantage of using a linked list to implement a stack in C?

A) Easier to manage memory

B) It does not have a fixed size

C) Faster push/pop operations

D) It is slower than array-based stacks

2. In a stack implemented using a linked list, where are the elements inserted?

A) At the bottom of the stack

B) In the middle of the stack

C) At the top of the stack

D) In any random position

3. What does the "top" pointer in a stack using a linked list point to?

A) The first element in the stack

B) The most recently added element

C) The last element in the stack

D) The second element from the top

4. Which operation is used to add an element to the stack in a linked list implementation?

A) pop()

B) push()

C) insert()

D) add()

5. Which of the following is a key advantage of a stack implemented using a linked list over an array implementation?

A) Fixed memory usage

B) Dynamic memory allocation

C) Simpler code

D) Faster element access

6. What will happen if you attempt to pop from an empty stack implemented using a linked list?

A) Stack underflow

B) Stack overflow

C) Program will crash

D) No operation

7. What is the time complexity of the push and pop operations for a stack implemented using a linked list?

A) O(n)

B) O(1)

C) O(log n)

D) O(n^2)

8. What is the typical data structure used to implement the stack using linked list?

A) Arrays

B) Pointers

C) Hash maps

D) Queues

9. Which of the following operations is typically done in constant time (O(1)) in a stack using linked list?

A) Insertion of a new element

B) Searching for an element

C) Deleting an element from the middle

D) Sorting the stack

10. How does memory management work in a stack using a linked list?

A) The memory size is fixed during stack creation

B) The memory is dynamically allocated and freed after each operation

C) Memory is allocated at the end of the program

D) It does not require memory management

Understanding factorial calculations is just the beginning—keep building your C programming skills with expert-led courses and hands-on learning.

How Can upGrad Help You Master Stack Using Linked List in C?

upGrad’s specialized courses on C programming provide a deep dive into topics like stack implementations using linked lists, recursion, and more. With hands-on projects and expert guidance, you will be able to implement stack-based algorithms in real-world applications, improving both your theoretical knowledge and practical coding skills.

Through upGrad’s expert-led curriculum, you’ll learn how to effectively manage dynamic memory, optimize stack operations, and understand the key differences between linked list-based and array-based implementations.

Explore our programs for C programming and data structures:

• Data Structures & Algorithms
• Advanced SQL: Functions and Formulas
• Learn Basic Python Programming
• JavaScript Basics from Scratch

You can also get personalized career counseling with upGrad to guide your career path, or visit your nearest upGrad center and start hands-on training today!

Similar Reads:

Explore C Tutorials: From Beginner Concepts to Advanced Techniques

Array in C: Introduction, Declaration, Initialisation and More

Exploring Array of Pointers in C: A Beginner's Guide

What is C Function Call Stack: A Complete Tutorial

Binary Search in C

Constant Pointer in C: The Fundamentals and Best Practices

Find Out About Data Structures in C and How to Use Them?

FAQs

1. What is the main advantage of using a stack with a linked list in C?

A stack using linked list in C with example allows dynamic memory allocation, meaning the stack can grow or shrink as needed, unlike a fixed-size array.

2. How does the stack using linked list algorithms work for dynamic memory management?

The stack using linked list algorithm efficiently manages memory by allocating space as elements are pushed and freeing space when they are popped, avoiding memory wastage.

3. Can a stack using a linked list in C have a fixed size?

No, a stack using linked list in C with example doesn’t have a fixed size, allowing it to grow or shrink as needed, unlike an array-based stack.

4. What happens if you try to pop from an empty stack?

The pop() operation checks if the stack is empty using the isEmpty operation. If the stack is empty, it will return an error message such as "Stack underflow."

5. How do I implement a peek operation in a stack using linked list in C?

The peek() operation returns the data from the top node without removing it, allowing you to view the top element without modifying the stack.

6. What is the time complexity of push and pop operations in a stack using linked list?

Both push and pop operations have a time complexity of O(1) because they only involve changing the top pointer and adjusting the linked list.

7. Why is a stack implemented using a linked list preferred over an array?

A stack using linked list in C with example allows dynamic resizing, making it more efficient in terms of memory usage compared to a static array-based stack.

8. How does the stack using linked list algorithms handle memory management?

The stack using linked list algorithm dynamically allocates memory for each element and frees it when the element is popped, ensuring memory is efficiently used.

9. Can a stack using linked lists be used for expression evaluation?

Yes, a stack using linked list in C with example is commonly used for tasks like expression evaluation and parsing, as it allows easy push and pop operations for operands and operators.

10. . Is it possible to implement multiple stacks using a single linked list?

Yes, you can implement multiple stacks within a single linked list by maintaining separate pointers for each stack, offering memory efficiency and flexibility.

11. What is the primary use case of a stack in real-world applications?

A stack using linked list in C with example is frequently used for undo functionality, expression parsing, function calls, and managing recursion, making it crucial in many real-world applications.

Take a Free C Programming Quiz

Answer quick questions and assess your C programming knowledge

Start Quiz