Stack Data Structure: Array and Linked List Implementation

Key Insights

• Array-based stacks offer better cache locality and simpler memory management, making them the default choice for most applications where maximum size is predictable or amortized resizing is acceptable.
• Linked list stacks eliminate resize operations entirely and provide true O(1) push/pop guarantees, but incur pointer overhead and scattered memory allocation that can hurt performance in practice.
• Understanding both implementations reveals that the “best” choice depends on your constraints—memory predictability, worst-case latency requirements, and whether you’re in a garbage-collected environment.

Introduction to Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last element added is the first one removed. Think of a stack of plates in a cafeteria—you add plates to the top and remove them from the top. Trying to grab a plate from the middle would be awkward and inefficient.

Real-world examples abound: your browser’s back button maintains a stack of visited pages, the undo feature in text editors pushes each action onto a stack, and function calls in virtually every programming language use a call stack to track execution context.

Stacks support four core operations:

• Push: Add an element to the top
• Pop: Remove and return the top element
• Peek (or Top): View the top element without removing it
• isEmpty: Check if the stack contains any elements

These operations should all run in O(1) time. If your stack implementation doesn’t achieve constant-time operations, something has gone wrong.

Stack Abstract Data Type (ADT)

Before diving into implementations, let’s define what a stack must do—its contract with the outside world. This abstraction lets us swap implementations without changing client code.

from abc import ABC, abstractmethod
from typing import TypeVar, Generic

T = TypeVar('T')

class Stack(ABC, Generic[T]):
    """Abstract base class defining the Stack ADT."""
    
    @abstractmethod
    def push(self, item: T) -> None:
        """Add item to the top of the stack."""
        pass
    
    @abstractmethod
    def pop(self) -> T:
        """Remove and return the top item. Raises exception if empty."""
        pass
    
    @abstractmethod
    def peek(self) -> T:
        """Return the top item without removing it. Raises exception if empty."""
        pass
    
    @abstractmethod
    def is_empty(self) -> bool:
        """Return True if the stack contains no items."""
        pass
    
    @abstractmethod
    def size(self) -> int:
        """Return the number of items in the stack."""
        pass

Every operation here should be O(1). The size() method is sometimes omitted from minimal stack definitions, but tracking it costs nothing and proves useful in practice.

Array-Based Implementation

The array-based stack is the workhorse implementation. You maintain an array and a top index pointing to the current top element (or the next empty slot, depending on convention).

Fixed-Size Implementation

Start simple with a fixed-capacity stack:

class ArrayStack(Stack[T]):
    """Stack implementation using a fixed-size array."""
    
    def __init__(self, capacity: int = 16):
        self._array: list = [None] * capacity
        self._top: int = -1  # -1 indicates empty stack
        self._capacity: int = capacity
    
    def push(self, item: T) -> None:
        if self._top >= self._capacity - 1:
            raise OverflowError("Stack is full")
        self._top += 1
        self._array[self._top] = item
    
    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        item = self._array[self._top]
        self._array[self._top] = None  # Help garbage collection
        self._top -= 1
        return item
    
    def peek(self) -> T:
        if self.is_empty():
            raise IndexError("Peek at empty stack")
        return self._array[self._top]
    
    def is_empty(self) -> bool:
        return self._top == -1
    
    def size(self) -> int:
        return self._top + 1

The fixed-size approach works when you know your maximum stack depth. Compiler implementations often use fixed stacks for parsing because grammar depth is bounded.

Dynamic Resizing

For general-purpose use, you need a stack that grows:

class DynamicArrayStack(Stack[T]):
    """Stack implementation with automatic resizing."""
    
    def __init__(self, initial_capacity: int = 16):
        self._array: list = [None] * initial_capacity
        self._top: int = -1
        self._capacity: int = initial_capacity
    
    def _resize(self, new_capacity: int) -> None:
        """Resize internal array to new_capacity."""
        new_array = [None] * new_capacity
        for i in range(self._top + 1):
            new_array[i] = self._array[i]
        self._array = new_array
        self._capacity = new_capacity
    
    def push(self, item: T) -> None:
        if self._top >= self._capacity - 1:
            self._resize(self._capacity * 2)  # Double the capacity
        self._top += 1
        self._array[self._top] = item
    
    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        item = self._array[self._top]
        self._array[self._top] = None
        self._top -= 1
        
        # Shrink if using less than 25% capacity (avoid thrashing)
        if self._top > 0 and self._top < self._capacity // 4:
            self._resize(self._capacity // 2)
        
        return item
    
    def peek(self) -> T:
        if self.is_empty():
            raise IndexError("Peek at empty stack")
        return self._array[self._top]
    
    def is_empty(self) -> bool:
        return self._top == -1
    
    def size(self) -> int:
        return self._top + 1

The doubling strategy gives amortized O(1) push operations. Individual pushes occasionally take O(n) for the copy, but spread across n operations, the average remains constant. The shrinking threshold at 25% (not 50%) prevents thrashing when operations alternate between push and pop at the boundary.

Linked List Implementation

A linked list stack uses nodes connected by pointers. Each push allocates a new node; each pop deallocates one. The head of the list serves as the stack top.

class Node(Generic[T]):
    """Node for linked list stack."""
    __slots__ = ('value', 'next')  # Memory optimization
    
    def __init__(self, value: T, next_node: 'Node[T]' = None):
        self.value = value
        self.next = next_node


class LinkedListStack(Stack[T]):
    """Stack implementation using a singly linked list."""
    
    def __init__(self):
        self._head: Node[T] = None
        self._size: int = 0
    
    def push(self, item: T) -> None:
        new_node = Node(item, self._head)
        self._head = new_node
        self._size += 1
    
    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        item = self._head.value
        self._head = self._head.next
        self._size -= 1
        return item
    
    def peek(self) -> T:
        if self.is_empty():
            raise IndexError("Peek at empty stack")
        return self._head.value
    
    def is_empty(self) -> bool:
        return self._head is None
    
    def size(self) -> int:
        return self._size

The elegance here is striking. Push creates a node pointing to the current head, then updates head. Pop saves the head’s value, advances head, and returns. No index management, no resize logic.

The __slots__ declaration prevents Python from creating a __dict__ for each node, reducing memory overhead significantly when you have thousands of nodes.

Implementation Comparison

Choose array-based when:

• You need predictable memory usage
• Cache performance matters (tight loops, numerical work)
• Maximum size is known or bounded
• You’re in a language without garbage collection (fewer allocations to track)

Choose linked list when:

• Worst-case O(1) is required (real-time systems)
• Stack size is highly unpredictable
• Memory fragmentation isn’t a concern
• You’re already using linked structures extensively

In practice, array-based stacks win most benchmarks due to cache effects. Modern CPUs prefetch contiguous memory, making sequential array access dramatically faster than pointer chasing.

Practical Application: Expression Evaluation

Let’s use our stack to solve a classic problem: validating balanced parentheses. This appears in compilers, JSON parsers, and code editors.

def is_balanced(expression: str) -> bool:
    """
    Check if parentheses, brackets, and braces are balanced.
    
    Examples:
        is_balanced("((a + b) * c)") -> True
        is_balanced("[(a + b]) * c") -> False
        is_balanced("{[()]}") -> True
    """
    stack = DynamicArrayStack[str]()
    
    matching = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    opening = set(matching.values())
    closing = set(matching.keys())
    
    for char in expression:
        if char in opening:
            stack.push(char)
        elif char in closing:
            if stack.is_empty():
                return False  # Closing without opening
            if stack.pop() != matching[char]:
                return False  # Mismatched pair
    
    return stack.is_empty()  # All opened must be closed


# Test cases
assert is_balanced("((a + b) * c)") == True
assert is_balanced("[(a + b]) * c") == False
assert is_balanced("{[()]}") == True
assert is_balanced("((())") == False
assert is_balanced("") == True

The algorithm pushes opening brackets and pops when encountering closing ones. If the popped bracket doesn’t match, or if we try to pop from an empty stack, the expression is unbalanced. At the end, an empty stack confirms all brackets were matched.

This pattern extends to more complex parsing: HTML tag matching, mathematical expression evaluation, and syntax validation in compilers.

Conclusion

Both implementations honor the stack contract, but they make different trade-offs. Array stacks trade occasional resize costs for cache-friendly memory layout. Linked list stacks trade pointer overhead for guaranteed constant-time operations.

For most applications, use your language’s built-in options:

• Python: Use list with append() and pop(). It’s a dynamic array underneath.
• Java: Use ArrayDeque over the legacy Stack class. Despite the name, it works perfectly as a stack.
• C++: Use std::stack with the default std::deque adapter, or specify std::vector for array behavior.
• JavaScript: Use arrays with push() and pop().

Understanding the underlying implementations helps you make informed decisions when built-ins aren’t suitable—embedded systems with tight memory, real-time applications requiring worst-case guarantees, or custom data structures where stacks are components.

The stack’s simplicity belies its importance. Master it, and you’ll recognize stack-shaped problems everywhere: undo systems, syntax parsing, depth-first traversal, and backtracking algorithms. It’s one of the fundamental building blocks of computer science, and knowing how to implement it from scratch gives you confidence to tackle more complex structures.