Stack Implementation with Linked Lists

In our last lesson, we explored the theoretical trade-offs between arrays and linked lists, concluding that linked lists shine when you need frequent, fast insertions and deletions at the beginning of a sequence. Today, we'll put that theory into practice by tackling a classic use case that perfectly illustrates this strength.

You will learn to implement a stack using a linked list, which will demonstrate the versatility and power of this dynamic data structure. In Module 10, you built a stack with a dynamically-sized array. Now you'll build an alternative version, giving you a deeper appreciation for how the same abstract data type (ADT) can be realized with different underlying structures, each with its own advantages.

1. The Core Concept: Mapping a Stack to a Linked List

Recall that a stack is a Last-In, First-Out (LIFO) structure. The two primary operations are push (add an element) and pop (remove an element), both of which occur at the "top" of the stack.

Our goal is to perform these operations in constant time, $O(1)$. Based on our last lesson, where in a linked list can we both insert and delete a node in $O(1)$ time? The answer is at the head of the list.

This gives us a simple and elegant mapping:

• The top of the stack will be the head of the linked list.
• push(value) becomes insertAtHead(value).
• pop() becomes deleteFromHead().

This visual representation makes the concept clear:

The head of the linked list serves as the top of our stack. All additions (push) and removals (pop) happen here, ensuring LIFO behavior and O(1) performance.

The following video provides an excellent explanation of why this approach is chosen and the performance implications of using the head versus the tail of the list.

2. Implementing the Stack Operations in C

Now that we have the guiding principle—top is head—let's translate this into C code. We'll need a Node structure and a single pointer, which we can call top, to keep track of the head of our list.

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

// A structure to represent a stack node
struct StackNode {
    int data;
    struct StackNode* next;
};

// A pointer to the top of the stack
struct StackNode* top = NULL;

With this setup, we can implement the core stack functions. The next video provides a line-by-line walkthrough of the code for push, pop, peek, and display.

Let's summarize the logic for each key function based on the video.

The push Function

This function adds a new element to the top of the stack.

1. Allocate Memory: Use malloc to create a new StackNode.
2. Check for Overflow: If malloc returns NULL, the system is out of memory. This is the linked-list equivalent of a "stack overflow".
3. Set Data: Assign the passed-in value to the data field of the new node.
4. Link to List: Set the next pointer of the new node to point to the current top.
5. Update Top: Update the top pointer to point to the new node, making it the new head of the list.

The pop Function

This function removes the top element from the stack.

1. Check for Underflow: If top is NULL, the stack is empty. There is nothing to pop.
2. Store a Temporary Pointer: Create a temporary pointer temp that points to the current top node. This is crucial so we don't lose track of the memory we need to deallocate.
3. Update Top: Move the top pointer to the next node in the list (top = top->next).
4. Free Memory: Call free(temp) to release the memory of the original top node. This step is non-negotiable; forgetting it leads to a memory leak, where your program consumes memory without ever releasing it.

This process is detailed in the DigitalOcean article "How to Implement a Stack in C".

3. A Complete Implementation

You now have all the conceptual pieces to build a fully functional stack using a linked list. The following resource provides a complete, well-structured C program that brings everything together.

4. Why Was This a Good Idea?

So, why go to the trouble of using a linked list when we already know how to implement a stack with an array? The answer lies in overcoming the array's biggest weakness: its fixed size.

• Dynamic Sizing: A linked list-based stack can grow and shrink as needed at runtime. You never have to decide on a MAX_SIZE beforehand. It will only fail if the entire system runs out of memory.
• No Wasted Memory: An array-based stack might have a capacity of 1000 but only hold 10 elements, wasting a significant amount of memory. The linked list implementation only allocates memory for the elements that actually exist.
• No "Stack Overflow" Errors: The dreaded stack overflow (from exceeding the array's capacity) is effectively eliminated.

This flexibility is what makes the linked list a "versatile" tool for this job. It adapts perfectly to the problem's needs without the rigid constraints of an array.

Conclusion

In this lesson, you have successfully combined your knowledge of linked lists and stacks to create a more flexible and robust data structure. This is a significant step, as you are now moving beyond implementing basic structures to choosing and building the right structure for a given task.

Key Takeaways:

• A stack can be efficiently implemented using a linked list by mapping the stack's top to the list's head.
• This approach ensures that push and pop operations are performed in constant time, $O(1)$.
• The main advantage of a linked list implementation is its dynamic size, which eliminates the risk of stack overflow and avoids memory waste from pre-allocating a fixed-size array.
• Proper memory management is critical: you must free the memory of a popped node to prevent memory leaks.

Preview of the Next Module:
So far, all the data structures we've worked with—arrays, linked lists, stacks, and queues—have been linear. They represent a sequence of items, one after another. In the next module, we will venture into the world of non-linear data structures, starting with trees. You will learn about the terminology of binary trees and discover how their hierarchical structure enables powerful new ways to organize and search for data, far more efficiently than a linear scan would allow.