Stack Implemented By Linked List

Overview

A stack is a Last-In, First-Out (LIFO) data structure: the most recently added element is the first one removed. Implementing a stack with a linked list is a simple and efficient way to support constant-time insertion and removal at the top by using the list’s head as the stack top.

Why Use a Linked List for a Stack?

• Dynamic size: Grows and shrinks on demand without resizing or pre-allocating capacity.
• O(1) push/pop: Inserting/removing at the head is constant time.
• Simple implementation: Only a head pointer and a node structure are required.
• Trade-offs: Extra pointer per node; potentially more heap allocations and less cache locality than an array-based stack.

Core Operations

• push(x): Insert x at the head; head becomes the new node.
• pop(): Remove and return the head value; update head to head.next.
• peek() or top(): Return the head value without removal.
• is_empty(): Check if head is null.
• size(): Track the number of elements.

How It Works

Structure Node:
    value
    next

Structure StackLL:
    head = null
    n = 0

    push(x):
        node = new Node
        node.value = x
        node.next = head
        head = node
        n = n + 1

    pop():
        if head is null: raise Underflow
        x = head.value
        head = head.next
        n = n - 1
        return x

    peek():
        if head is null: raise Underflow
        return head.value

    is_empty():
        return head is null

    size():
        return n

Visual intuition:

top -> [value: 7 | next] -> [value: 3 | next] -> [value: 1 | next] -> null

Complexity

• Time: push O(1), pop O(1), peek O(1), is_empty O(1)
• Space: O(n) for n elements, plus per-node pointer overhead

Implementation Notes

• Singly vs doubly linked: A singly linked list is sufficient; you only need fast access to the top.
• Sentinel (dummy) head: Optional; can simplify edge-case checks at the cost of one extra node.
• Error handling: Decide how to handle underflow (exceptions, error codes, or a special value if the type permits).
• Memory management: In manual memory languages, ensure popped nodes are freed; otherwise, you risk leaks.
• Thread safety: Not thread-safe by default; add synchronization if used concurrently.
• Generics: Parameterize the value type for type safety.

Comparison: Linked List Stack vs Array-Based Stack

• Linked list: No resizing; stable O(1) push/pop; extra pointer per node; more allocations.
• Array: Better cache locality; may need resizing; push can be amortized O(1); fixed capacity if not resizable.

Small Python Example

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class StackLL:
    def __init__(self):
        self._head = None
        self._size = 0

    def push(self, x):
        self._head = Node(x, self._head)
        self._size += 1

    def pop(self):
        if self._head is None:
            raise IndexError
        x = self._head.value
        self._head = self._head.next
        self._size -= 1
        return x

    def peek(self):
        if self._head is None:
            raise IndexError
        return self._head.value

    def is_empty(self):
        return self._head is None

    def __len__(self):
        return self._size

Use Cases

• Expression evaluation and parsing (postfix, prefix, infix conversions)
• Balanced parentheses and delimiter checking
• Backtracking and depth-first search helpers
• Undo and redo functionality

Common Pitfalls

• Forgetting to update the head on push or pop.
• Not handling underflow when popping or peeking an empty stack.
• Memory leaks in manual memory environments by not freeing nodes.
• Using tail operations, which turn pop into O(n); always operate at the head.

Next Topic