Implementing a Stack Using a Linked List in C

Welcome to another installment of our C Language Series! In this guide, we'll dive deep into implementing one of the most fundamental data structures: a Stack. While stacks can be implemented using arrays, we'll explore a more dynamic and flexible approach: using a Linked List. This method overcomes many limitations of array-based stacks, providing a robust solution for managing data.

Understanding the Stack Data Structure

A stack is a linear data structure that follows a particular order in which operations are performed. The order is LIFO (Last In, First Out). Imagine a stack of plates: you can only add a new plate to the top, and you can only remove the topmost plate.

The primary operations associated with a stack are:

• Push: Adds an element to the top of the stack.
• Pop: Removes the topmost element from the stack and returns it.
• Peek (or StackTop): Returns the topmost element without removing it.
• isEmpty: Checks if the stack is empty.
• isFull: Checks if the stack is full (more relevant for array-based stacks, but for linked lists, it checks for memory availability).

Why Use a Linked List for Stack Implementation?

While arrays offer a simple way to implement stacks, they come with inherent limitations, primarily a fixed size. Once an array is declared, its size cannot be changed. This means you might face a stack overflow if you try to push more elements than the array can hold, or waste memory if you allocate a large array but only use a small portion of it.

Implementing a stack using a linked list provides significant advantages:

• Dynamic Size: The stack can grow or shrink as needed, limited only by the available memory in the system. There's no fixed size constraint.
• Efficient Memory Usage: Memory is allocated dynamically for each node as elements are pushed, preventing wastage.
• No Overflow Issues (mostly): A linked list stack will only overflow if the entire system runs out of heap memory, which is much less common than hitting a fixed array limit.

Core Concepts for Linked List Stack

To implement a stack using a linked list, we need two main components:

1. Node Structure: Each element in our stack will be a node in the linked list. A node typically contains two parts:
   • The data element (the actual value stored).
   • A next pointer, which points to the next node in the list (or NULL if it's the last node).
2. top Pointer: We need a special pointer, usually named top, which will always point to the topmost node of the stack. In a linked list stack, the top pointer essentially serves as the head of our linked list.

Node Structure Definition

First, let's define our node structure in C:

#include <stdio.h>
#include <stdlib.h> // For malloc and free

// Node structure for the linked list stack
struct Node {
    int data;          // Data part of the node
    struct Node *next; // Pointer to the next node
};
    

Our stack will be managed by a struct Node *top pointer, initialized to NULL for an empty stack.

Implementing Stack Operations

1. `isEmpty()`: Checking if the Stack is Empty

An empty stack means there are no elements. In our linked list implementation, this translates to the top pointer being NULL.

int isEmpty(struct Node *top) {
    return (top == NULL);
}
    

2. `isFull()`: Checking for Stack Overflow (Memory Exhaustion)

Unlike array-based stacks, a linked list stack is rarely "full" in the traditional sense. It only becomes full if the dynamic memory allocation (malloc) fails due to the system running out of heap memory. We can simulate this check by trying to allocate a new node.

int isFull() {
    struct Node *n = (struct Node *) malloc(sizeof(struct Node));
    if (n == NULL) {
        return 1; // Memory allocation failed, stack is full
    } else {
        free(n);  // Free the temporary node
        return 0;
    }
}
    

3. `push()`: Adding an Element to the Stack

When pushing an element, we create a new node, assign the data to it, and then make this new node the new top of the stack. The next pointer of the new node will point to the previous top.

struct Node* push(struct Node *top, int x) {
    if (isFull()) {
        printf("Stack Overflow! Cannot push %d, no memory left.\n", x);
        return top; // Return original top if overflow
    }
    struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
    if (newNode == NULL) { // Additional safety check
        printf("Stack Overflow! Memory allocation failed.\n");
        return top;
    }
    newNode->data = x;
    newNode->next = top; // Link new node to current top
    top = newNode;       // New node becomes the new top
    printf("Pushed: %d\n", x);
    return top;          // Return the new top pointer
}
    

Explanation:

1. First, we check if the system can even allocate memory for a new node using isFull().
2. A new newNode is allocated using malloc().
3. The data of newNode is set to the value x.
4. The next pointer of newNode is made to point to the current top (effectively linking it above the previous top).
5. The top pointer is then updated to point to newNode, making it the new topmost element.
6. The function returns the updated top pointer.

4. `pop()`: Removing an Element from the Stack

Popping involves removing the topmost element. We first check for underflow (empty stack), then retrieve the data from the top node, move the top pointer to the next node, and finally free the memory of the old top node.

struct Node* pop(struct Node *top, int *poppedValue) {
    if (isEmpty(top)) {
        printf("Stack Underflow! Cannot pop, stack is empty.\n");
        *poppedValue = -1; // Indicate an error or invalid value
        return top;        // Return original top if underflow
    }
    struct Node *temp = top;   // Store current top in a temporary pointer
    *poppedValue = temp->data; // Retrieve data before freeing
    top = top->next;           // Move top to the next node
    free(temp);                // Free the old top node's memory
    printf("Popped: %d\n", *poppedValue);
    return top;                // Return the new top pointer
}
    

Explanation:

1. We check for isEmpty() to prevent popping from an empty stack (stack underflow).
2. A temporary pointer temp is used to hold the current top node.
3. The data from temp is stored in *poppedValue (passed by reference).
4. The top pointer is updated to point to temp->next, making the second element the new top.
5. The memory occupied by the original top node (pointed to by temp) is freed using free().
6. The function returns the updated top pointer.

5. `peek()`: Getting the Top Element without Removing

The peek() operation simply returns the data of the topmost element without modifying the stack. We just need to check if the stack is not empty.

int peek(struct Node *top) {
    if (isEmpty(top)) {
        printf("Stack is empty, no element to peek.\n");
        return -1; // Indicate an error or invalid value
    }
    return top->data;
}
    

6. `display()`: Traversing and Printing Stack Elements

To see the elements in the stack, we can traverse the linked list from top to NULL.

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

Putting It All Together: A Complete C Example

Here's the full C code demonstrating the linked list stack implementation and its operations:

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

// Node structure for the linked list stack
struct Node {
    int data;
    struct Node *next;
};

// Function prototypes
int isEmpty(struct Node *top);
int isFull(); // Checks for memory allocation failure
struct Node* push(struct Node *top, int x);
struct Node* pop(struct Node *top, int *poppedValue);
int peek(struct Node *top);
void display(struct Node *top);

int main() {
    struct Node *top = NULL; // Initialize top of the stack as NULL

    printf("--- Pushing elements ---\n");
    top = push(top, 10);
    top = push(top, 20);
    top = push(top, 30);
    top = push(top, 40);
    display(top);

    printf("\n--- Peeking ---\n");
    int topElement = peek(top);
    if (topElement != -1) {
        printf("Top element is: %d\n", topElement);
    }

    printf("\n--- Popping elements ---\n");
    int value;
    top = pop(top, &value); // Pop 40
    if (value != -1) {
        printf("Popped value: %d\n", value);
    }
    display(top);

    top = pop(top, &value); // Pop 30
    if (value != -1) {
        printf("Popped value: %d\n", value);
    }
    display(top);

    printf("\n--- Peeking after pops ---\n");
    topElement = peek(top);
    if (topElement != -1) {
        printf("Top element is: %d\n", topElement);
    }

    printf("\n--- Pushing more elements ---\n");
    top = push(top, 50);
    display(top);

    printf("\n--- Popping all remaining elements ---\n");
    while (!isEmpty(top)) {
        top = pop(top, &value);
        if (value != -1) {
            printf("Popped value: %d\n", value);
        }
    }
    display(top); // Stack should be empty now

    printf("\n--- Trying to pop from an empty stack ---\n");
    top = pop(top, &value); // Should result in Stack Underflow

    printf("\n--- Trying to peek an empty stack ---\n");
    peek(top); // Should result in Stack empty message

    // Free any remaining nodes (though pop should have freed them)
    // This loop ensures all memory is freed if program terminates early or improperly
    struct Node *current = top;
    while (current != NULL) {
        struct Node *next = current->next;
        free(current);
        current = next;
    }
    top = NULL;

    return 0;
}

// Function to check if the stack is empty
int isEmpty(struct Node *top) {
    return (top == NULL);
}

// Function to check if the stack is full (memory allocation failed)
int isFull() {
    struct Node *n = (struct Node *) malloc(sizeof(struct Node));
    if (n == NULL) {
        return 1; // Memory allocation failed, stack is full
    } else {
        free(n);
        return 0;
    }
}

// Function to push an element onto the stack
struct Node* push(struct Node *top, int x) {
    if (isFull()) {
        printf("Stack Overflow! Cannot push %d, no memory left.\n", x);
        return top;
    }
    struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Stack Overflow! Memory allocation failed.\n");
        return top;
    }
    newNode->data = x;
    newNode->next = top;
    top = newNode;
    return top;
}

// Function to pop an element from the stack
struct Node* pop(struct Node *top, int *poppedValue) {
    if (isEmpty(top)) {
        printf("Stack Underflow! Cannot pop, stack is empty.\n");
        *poppedValue = -1;
        return top;
    }
    struct Node *temp = top;
    *poppedValue = temp->data;
    top = top->next;
    free(temp);
    return top;
}

// Function to get the top element without removing it
int peek(struct Node *top) {
    if (isEmpty(top)) {
        printf("Stack is empty, no element to peek.\n");
        return -1;
    }
    return top->data;
}

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

Advantages and Considerations

Using a linked list for stack implementation offers great flexibility. However, it's also important to note that each node requires a small overhead for the pointer storage, and memory allocation can be slightly slower than direct array access (though often negligible for most applications).

• Advantages: Dynamic size, efficient memory usage (no pre-allocation), no fixed overflow limits.
• Considerations: Slight memory overhead per node for the next pointer, potential for slightly slower access due to dynamic memory allocation and pointer dereferencing compared to contiguous array memory.

Conclusion

Implementing a stack using a linked list in C provides a powerful and dynamic way to manage LIFO data. By understanding the core operations and how they interact with the linked list structure, you've gained a valuable tool in your data structures arsenal. This approach is fundamental for various applications, including function call stacks, expression evaluation, and backtracking algorithms.

Stay tuned for more in our C Language Series!