# Arrays vs Linked Lists: The Benchmark Textbooks Don't Run

> The textbook says linked lists win at insertion, O(1) vs O(n). Run the benchmark and the array wins insertion-heavy workloads too — often by 10x. The memory hierarchy voted, and it didn't vote for pointers.

URL: https://harshith.in/blog/arrays-vs-linked-lists/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: algorithms, performance, memory

Here's a benchmark Bjarne Stroustrup liked to show: keep a sequence of N random
integers in sorted order — for each new element, find its position and insert it;
then delete elements one by one at random positions. Insertion and deletion
dominate, so by the textbook, `std::list` should crush `std::vector`. It loses.
Not narrowly — for N in the hundreds of thousands, the vector wins by an order of
magnitude, and the gap *grows* with N. Every systems interview that ends at
"linked list: O(1) insertion" stops one question short of the truth.

## Where the Textbook Analysis Leaks

The O(1) insertion claim is true and useless on its own, for two reasons.

**You have to get there first.** Insertion at a *known node* is O(1); finding the
position is O(n) — and it's the worst kind of O(n). Each `node = node->next` is a
dependent load to an unpredictable heap address: no prefetching, no parallelism,
frequently a full cache miss. Call it ~100 ns per step. The array's O(n) shift,
by contrast, is `memmove` — sequential, prefetched, SIMD-copied, moving 16+
elements per cache line at tens of GB/s. The list's *traversal* costs more than
the array's *shifting*.

```text
   list:   [find: n/2 cache misses] + [relink: free]     ≈ 50ns × n/2
   vector: [find: binary search or scan, cached] + [memmove] ≈ ~1ns × n/2
```

**Each node also costs you at allocation.** One `malloc` per node (vs one
amortized growth per thousands of pushes), 16 bytes of pointer overhead plus
allocator metadata per element — for a list of ints, memory blows up 4–6× — and
nodes scatter across the heap, so even a "sequential" walk of the list is random
access to memory. Adjacent-in-list is not adjacent-in-RAM.

## What Vectors Pay

Honesty requires the other column. Vectors have three real costs: growth
reallocation invalidates every pointer/iterator into the container (the #1 vector
bug: `push_back` during iteration); a huge vector needs one huge contiguous
allocation; and worst-case `push_back` latency is O(n) when growth hits — the
amortized O(1) is an *average*, which matters if you have a p99 budget. And
`std::deque` quietly fixes two of these (chunked storage: stable-ish references,
no mega-allocation) while keeping indexing O(1) — it's the most underused
container in the language.

## Where Lists Actually Win

Linked lists survive in niches where their one superpower — **O(1) splice at a
node you already hold, without invalidating anything** — is the entire workload:

- **Intrusive lists in kernels and allocators.** The node lives *inside* the
  object (`list_head` in Linux), so there's no per-node allocation and the object
  is already in cache when you touch its links. Every task, timer, and free chunk
  in your kernel is on one. This is the honest home of linked lists.
- **LRU caches**: hash map gives you the node in O(1), list moves it to the front
  in O(1). The traversal weakness never fires because you never traverse.
- **Lock-free structures and free lists**, where a single-pointer CAS is the
  update primitive.

Note the common shape: something *else* (a hash map, containment in the object)
eliminates the O(n) find, leaving only the O(1) relink. A linked list you
linearly search is almost always the wrong structure.

## The Decision Procedure

Default to the contiguous option (`vector`, or a ring buffer for queues — both
ends O(1), still contiguous). Reach for a list only when you can say which
mechanism hands you the node without searching, and what invalidation problem
the list is solving. And when the choice matters, run the Stroustrup benchmark
on *your* element size and *your* N — with 4 KB elements the copy costs start
mattering and the answer can flip (or better: vector of pointers, indirection
only where elements are fat).

## Takeaways

- List insertion is O(1) only after an O(n) find, and list-O(n) is cache-miss-O(n)
  — ~100× the per-step cost of array-O(n).
- Per-node allocation adds latency, 2–6× memory overhead, and heap scatter.
- Vectors' real costs are iterator invalidation and reallocation latency spikes —
  know them, they're the bugs you'll actually write.
- Lists earn their place when something else provides O(1) access to the node:
  intrusive kernel lists, LRU via hashmap+list, lock-free stacks.
- `deque` and ring buffers cover most "but I insert at both ends" cases while
  staying contiguous.