Difference Between Array-Based and Linked List-Based Stack Implementations

Array-based stacks leverage contiguous memory and dynamic arrays for superior cache locality and amortized O(1) operations, while linked list-based stacks use node pointers to guarantee consistent O(1) performance without resizing costs but incur higher per-element memory overhead.

The choice between array-based and linked list-based stack implementations fundamentally impacts memory efficiency, cache performance, and operational latency in algorithmic applications. This article examines the concrete architectural differences between these approaches as implemented in the krahets/hello-algo repository, analyzing how each manages LIFO (last-in-first-out) operations while handling memory layout and growth strategies.

Core Stack Operations

Both implementations adhere to the standard stack abstract data type, supporting three fundamental operations with O(1) time complexity:

• push – Insert an element at the top of the stack
• pop – Remove and return the top element
• peek – Access the top element without removal

While the logical interface remains identical, the underlying storage mechanisms and performance characteristics differ significantly between contiguous array storage and pointer-based node linking.

Internal Architecture Comparison

Array-Based Stack Implementation

The array-based implementation, located in codes/python/chapter_stack_and_queue/array_stack.py, utilizes a Python list as its backing store. This approach stores elements in contiguous memory locations, with the stack top represented by the last index of the array (self._stack[-1]).

Key architectural characteristics include:

• Dynamic resizing: When the underlying array reaches capacity, the system allocates a larger memory block (typically 1.5× to 2× the current size) and copies existing elements, resulting in amortized O(1) push operations
• Cache locality: Excellent CPU cache performance due to contiguous memory layout, allowing efficient prefetching of subsequent elements
• Memory overhead: Minimal per-element overhead, though the array may maintain unused capacity between growth cycles to optimize for future insertions

Linked List-Based Stack Implementation

The linked list-based implementation, found in codes/python/chapter_stack_and_queue/linkedlist_stack.py, constructs a singly-linked list where each node contains a value and a reference to the next node. The stack top corresponds to the head of the list (self._peek), enabling constant-time head insertion and removal.

Key architectural characteristics include:

• Node allocation: Each push operation allocates a new ListNode object individually, with no bulk resizing required
• Pointer overhead: Every element incurs additional memory cost for the next pointer (approximately 8 bytes on 64-bit systems) plus object headers
• Cache performance: Poorer locality compared to arrays, as nodes may be scattered throughout the heap, causing increased cache misses
• Consistent latency: Operations guarantee strict O(1) time without occasional latency spikes from array resizing events

Code Implementation Comparison

ArrayStack Implementation

The ArrayStack class in codes/python/chapter_stack_and_queue/array_stack.py wraps Python's built-in list to provide type-hinted stack operations:

class ArrayStack:
    """基于数组实现的栈"""
    def __init__(self):
        self._stack: list[int] = []          # contiguous storage

    def push(self, item: int):
        self._stack.append(item)             # O(1) amortised

    def pop(self) -> int:
        if not self._stack:
            raise IndexError("栈为空")
        return self._stack.pop()             # O(1)

    def peek(self) -> int:
        if not self._stack:
            raise IndexError("栈为空")
        return self._stack[-1]               # O(1)

    def size(self) -> int:
        return len(self._stack)

LinkedListStack Implementation

The LinkedListStack class in codes/python/chapter_stack_and_queue/linkedlist_stack.py manages node references explicitly using ListNode objects:

class LinkedListStack:
    """基于链表实现的栈"""
    def __init__(self):
        self._peek: ListNode | None = None   # head of the list

        self._size: int = 0

    def push(self, val: int):
        node = ListNode(val)                 # allocate a new node

        node.next = self._peek                # O(1) head insertion

        self._peek = node
        self._size += 1

    def pop(self) -> int:
        if self._peek is None:
            raise IndexError("栈为空")
        val = self._peek.val
        self._peek = self._peek.next          # O(1) head removal

        self._size -= 1
        return val

    def peek(self) -> int:
        if self._peek is None:
            raise IndexError("栈为空")
        return self._peek.val                # O(1)

    def size(self) -> int:
        return self._size

Performance and Memory Trade-offs

When selecting between these array-based and linked list-based stack implementations, consider the following operational characteristics:

Metric	Array-Based Stack	Linked-List-Based Stack
Time Complexity (push/pop)	O(1) amortized; occasional O(n) resizing	Strict O(1); no resizing events
Cache Locality	Excellent – contiguous memory benefits CPU caches	Poorer – scattered nodes increase cache misses
Memory Overhead	Low per-element; potential unused capacity in array	High per-element – extra pointer per node (≈8 bytes on 64-bit)
Latency Predictability	Variable due to resizing spikes	Consistent operation times
Random Access	Possible (though not recommended for stacks)	Not available without traversal

Choosing the Right Implementation

Select array-based stacks when:

• Working with bounded or predictable maximum sizes
• Optimizing for CPU cache performance in tight loops
• Minimizing per-element memory overhead is critical
• Implementing expression evaluators, parsers, or depth-first search algorithms where raw throughput matters

Select linked-list-based stacks when:

• The stack size is unbounded or highly variable
• Consistent latency is required without resizing pauses
• Memory fragmentation from array expansion is unacceptable
• Building long-running server applications where predictable performance outweighs cache efficiency

Summary

• Array-based stacks utilize contiguous memory blocks with dynamic resizing, offering superior cache locality and minimal per-element overhead at the cost of occasional O(n) resizing operations.
• Linked-list-based stacks employ node pointers for consistent O(1) operations without resizing spikes, trading cache performance for predictable latency and incurring additional pointer memory overhead.
• Both implementations satisfy the standard LIFO stack interface with O(1) push and pop operations, making the choice dependent on specific workload characteristics, memory constraints, and performance requirements.
• The krahets/hello-algo repository provides production-ready implementations in codes/python/chapter_stack_and_queue/array_stack.py and codes/python/chapter_stack_and_queue/linkedlist_stack.py.

Frequently Asked Questions

Which stack implementation offers better cache performance?

Array-based stacks provide superior cache locality because elements are stored in contiguous memory locations, allowing CPU caches to prefetch subsequent elements efficiently. Linked-list-based stacks suffer from cache misses because nodes are allocated independently and scattered throughout the heap memory.

Do both implementations guarantee O(1) time complexity for push and pop?

Yes, both provide O(1) time complexity, but with different guarantees. Array-based stacks offer amortized O(1) performance, occasionally requiring O(n) time when resizing the underlying array. Linked-list-based stacks provide strict O(1) performance for every operation since they allocate nodes individually without resizing events.

When should I choose a linked list stack over an array stack?

Choose a linked-list-based stack when you require consistent latency without resizing pauses, when the maximum stack size is unpredictable or unbounded, or when memory fragmentation from array expansion is unacceptable in long-running applications. This implementation is ideal for server environments where predictable performance outweighs raw throughput.

How does memory overhead compare between the two approaches?

Array-based stacks minimize per-element overhead by storing raw values in a contiguous block, though they may allocate unused capacity (typically 1.5× to 2× the current size) to accommodate growth. Linked-list-based stacks incur higher per-element overhead because each node requires an additional pointer field (approximately 8 bytes on 64-bit systems) plus object headers, but they allocate exactly the memory needed for existing elements.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}