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

> Explore array-based vs linked list-based stack implementations. Understand cache locality, O(1) operations, memory overhead, and resizing costs for efficient data structure choices.

- Repository: [Yudong Jin/hello-algo](https://github.com/krahets/hello-algo)
- Tags: comparison
- Published: 2026-02-25

---

**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`](https://github.com/krahets/hello-algo/blob/main/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`](https://github.com/krahets/hello-algo/blob/main/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`](https://github.com/krahets/hello-algo/blob/main/codes/python/chapter_stack_and_queue/array_stack.py) wraps Python's built-in list to provide type-hinted stack operations:

```python
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`](https://github.com/krahets/hello-algo/blob/main/codes/python/chapter_stack_and_queue/linkedlist_stack.py) manages node references explicitly using `ListNode` objects:

```python
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`](https://github.com/krahets/hello-algo/blob/main/codes/python/chapter_stack_and_queue/array_stack.py) and [`codes/python/chapter_stack_and_queue/linkedlist_stack.py`](https://github.com/krahets/hello-algo/blob/main/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.