OneNoughtOne
0/361
Loading content...
Read aloud is unavailable in this browser.
In the previous module, we explored how arrays can serve as the underlying data structure for stacks. Array-based stacks are elegant, cache-friendly, and remarkably efficient—but they carry a fundamental limitation: fixed capacity. When you create an array-based stack with a capacity of 100 elements, that 101st push operation either fails catastrophically or triggers an expensive resizing operation.
This brings us to an elegant alternative: the linked list-based stack. By leveraging the dynamic nature of linked lists, we can create stacks that grow and shrink organically with demand, never running into capacity limits, and performing every operation in constant time—guaranteed, not amortized.
The marriage between singly linked lists and stacks isn't just convenient—it's natural. The very structure of a singly linked list mirrors the access pattern of a stack so precisely that implementing a stack becomes almost trivial once you understand both data structures.
By the end of this page, you will understand why singly linked lists are ideally suited for stack implementation. You'll see how the structural properties of linked lists map directly to stack semantics, explore the conceptual model that makes this implementation intuitive, and appreciate the trade-offs that inform when to choose linked lists over arrays for your stacks.
Before we bridge linked lists to stacks, let's refresh our understanding of the singly linked list—the data structure that will serve as our stack's foundation.
The singly linked list is a sequence of nodes where each node contains:
The list maintains a head pointer that references the first node. The last node's next pointer is null, signifying the end of the list.
Key Properties of Singly Linked Lists:
Notice that operations at the head of a singly linked list are O(1), while operations at the tail are O(n) without a tail pointer. This asymmetry is precisely why stacks map so naturally to linked lists—stacks only need efficient access to one end!
To understand why singly linked lists are a natural fit for stacks, let's revisit what a stack fundamentally requires:
Stack operations (ADT perspective):
push(element): Add an element to the toppop(): Remove and return the element from the toppeek() / top(): View the top element without removing itisEmpty(): Check if the stack is emptysize(): Return the number of elements (optional)Observe the pattern: Every single operation involves only the top of the stack. We never need to access the middle or bottom. This is the LIFO (Last-In, First-Out) principle in action—and it maps perfectly to head operations in a linked list.
| Stack Operation | Linked List Equivalent | Time Complexity |
|---|---|---|
| push(element) | Insert at head | O(1) |
| pop() | Remove from head | O(1) |
| peek() / top() | Read head node's value | O(1) |
| isEmpty() | Check if head is null | O(1) |
| size() | Maintain a counter (or traverse) | O(1) with counter |
The mapping is not just efficient—it's direct.
When we push onto a stack, we're conceptually placing an item on top of a pile. In a linked list, inserting at the head places a new node at the front of the chain. Both operations add to the 'top' end.
When we pop from a stack, we remove the topmost item. In a linked list, removing the head node accomplishes exactly this—we're always working with the most recently added element.
This conceptual alignment isn't coincidental. It reflects a deep structural correspondence between the LIFO access pattern and the asymmetric efficiency of singly linked lists.
Good data structure design often involves recognizing when the structural properties of one abstraction naturally satisfy the requirements of another. The linked list stack is a textbook example: the inherent O(1) head operations of linked lists perfectly match the single-end access pattern of stacks.
Let's build a mental model for how a linked list-based stack looks and behaves. Understanding this visualization is crucial for implementing and debugging linked stacks correctly.
The core idea: The head of the linked list is the top of the stack.
Imagine a vertical stack of plates. The top plate (the one you'd grab first) corresponds to the head node of our linked list. Each plate below connects to the one above it through a 'next' pointer.
Translating to linked list terminology:
State transitions during push:
When we push a new element (say, 40) onto our stack containing [30, 20, 10]:
next pointer to the current head (node with 30)The new node becomes the head, representing the new top of the stack. The operation completes in constant time regardless of stack size.
Unlike array-based stacks where resizing requires copying all elements, linked list pushes never move existing data. Each node stays in place—we simply update pointer references. This is a fundamental advantage when dealing with large elements or memory-constrained environments.
To fully appreciate the linked list approach, let's contrast it structurally with array-based stacks. Both implement the same abstract data type (stack), but their internal organizations are fundamentally different.
| Property | Array-Based Stack | Linked List Stack |
|---|---|---|
| Memory layout | Contiguous block | Scattered nodes connected by pointers |
| Capacity | Fixed or dynamically resized | Unbounded (limited only by system memory) |
| Memory per element | Element size only | Element size + pointer overhead (8 bytes on 64-bit) |
| Cache performance | Excellent (spatial locality) | Poor (nodes may be scattered in memory) |
| Top location | Tracked by index | Always at head pointer |
| Growth mechanism | Array copy/resize | Single node allocation |
| Shrinkage | Often doesn't release memory | Immediate memory release per pop |
Memory layout visualized:
Array Stack Memory:
Address: 0x1000 0x1001 0x1002 0x1003 0x1004
[ 10 ][ 20 ][ 30 ][ ][ ]
↑ ↑
base top
All elements occupy adjacent memory addresses. The top index tracks where the next push goes.
Linked List Stack Memory:
Address: 0x3000 → 0x5000 → 0x2000 → null
Value: [ 30 ] [ 20 ] [ 10 ]
↑
head
Nodes can be anywhere in memory. Pointers maintain the logical order.
The scattered memory layout of linked lists means cache misses are more likely when traversing or accessing elements. For stacks, where we only ever access the top element, this is less critical—but it can matter in performance-sensitive applications. Array stacks win on cache efficiency; linked stacks win on flexibility and guaranteed O(1) operations.
Understanding when to use a linked list stack versus an array stack is crucial for practical software engineering. The choice depends on your specific requirements and constraints.
In practice, many standard library stack implementations use dynamic arrays (like Java's Stack extends Vector, or C++ std::stack with std::deque) because their amortized O(1) performance and cache benefits outweigh the occasional resize cost. However, linked list stacks remain valuable in specific domains: embedded systems, memory-constrained environments, and applications requiring strict real-time guarantees.
Before we implement operations, let's define the fundamental building block: the Node.
A node in our linked list stack is a simple container with two components:
Generic Node Definition:
In typed languages, we typically make the Node generic to support stacks of any element type:
123456789101112131415161718192021222324
// Generic Node class for a linked list stackclass StackNode<T> { data: T; // The value stored in this node next: StackNode<T> | null; // Reference to the next node (below this one) constructor(data: T) { this.data = data; this.next = null; }} // Example usage:// For a stack of numbers:const numberNode = new StackNode<number>(42); // For a stack of strings:const stringNode = new StackNode<string>("hello"); // For a stack of custom objects:interface Task { id: number; name: string;}const taskNode = new StackNode<Task>({ id: 1, name: "Complete project" });Memory footprint of a node:
Each node consumes:
For example, in a stack storing 32-bit integers:
This 3x overhead is the price we pay for dynamic flexibility. For larger objects, this overhead becomes proportionally smaller and often negligible.
In some languages, the Node class can be defined as an inner class within the Stack class. This encapsulation prevents external code from directly manipulating nodes—preserving the stack abstraction. It's a good practice for maintaining invariants and hiding implementation details.
With our Node structure defined, let's outline the LinkedStack class itself. This skeleton shows the fields and method signatures—we'll implement each method in detail in subsequent pages.
Key design decisions:
head (or top) pointer—no tail pointer needed since we never access the other end.1234567891011121314151617181920
class LinkedStack<T> { private top: StackNode<T> | null; // Points to the top of the stack private count: number; // Number of elements in the stack constructor() { this.top = null; // Empty stack starts with null top this.count = 0; // No elements initially } // Core stack operations (to be implemented) push(element: T): void { /* ... */ } pop(): T { /* ... */ } peek(): T { /* ... */ } isEmpty(): boolean { /* ... */ } size(): number { /* ... */ } // Optional utility methods clear(): void { /* ... */ } toString(): string { /* ... */ }}Invariants we must maintain:
top is null if and only if the stack is emptycount accurately reflects the number of nodes reachable from topnext = nullnext pointers always terminates)These invariants are crucial for correctness. Every method we implement must preserve them, and we can use them to reason about our code's behavior.
Notice that top and count are private. External code should interact with the stack only through its public methods. This prevents invariant violations—for example, external code setting count to an incorrect value or modifying top directly.
We've established the conceptual foundation for implementing stacks using singly linked lists. Let's consolidate our key insights:
What's next:
With the conceptual model firmly in place, we'll move to the practical implementation. The next page examines why the head position specifically is the optimal choice for representing the top of our stack—and what would happen if we tried a different approach.
You now understand why singly linked lists are a natural and powerful choice for implementing stacks. The structural properties align perfectly with stack semantics, enabling guaranteed O(1) operations with unbounded capacity. Next, we'll explore why the head position specifically serves as the ideal stack top.