Linked Lists Dead? Why O(1) Isn't Always Faster Than O(N) — Stroustrup & Cache Reality

The article opens with a heated discussion sparked by a Zhihu question: whether linked lists are obsolete. Three camps emerge — "linked lists are dead," "linked lists lose to arrays," and "linked lists have moved behind the scenes." The core conflict is between textbook Big-O analysis and modern hardware reality.

Linked Lists Were Once the Hero

In data-structure courses, arrays provide fast lookup while linked lists provide fast insertion/deletion: array insertion is O(n) due to element shifting, linked list insertion is O(1) by pointer manipulation. This conclusion assumes memory access is free and only basic operation counts matter.

The Memory Wall and Cache

CPU speeds have grown exponentially while DRAM latency has improved slowly, creating a "memory wall." Modern CPUs bridge this with multi-level caches (L1/L2/L3). Two key mechanisms matter:

Cache-line prefetch: CPUs load data in 64-byte cache lines; accessing one int brings neighbors into cache.

Hardware prefetcher: Detects linear access patterns and preloads subsequent data.

This is the Locality principle: spatially and temporally adjacent data are favored. Linked lists violate both: nodes are scattered in heap memory, each pointer dereference may cause a cache miss, and the "pointer chasing" pattern defeats hardware prefetching. Array insertion uses memcpy — contiguous and prefetch-friendly — so actual runtime often favors arrays despite higher Big-O.

Stroustrup's Classic Experiment

At Going Native 2012, Bjarne Stroustrup presented an experiment from Jon Bentley: insert random integers in sorted order, then delete at random positions. std::list lost decisively to std::vector even though the workload consisted entirely of insertions and deletions — operations where linked lists should theoretically excel. Stroustrup later clarified on isocpp.org that his point was not that lists are evil, but that cache effects dominate . He gave three principles:

don't store data unnecessarily keep data compact access memory in a predictable manner

His practical advice: default to std::vector; use contiguous representation unless there is a compelling reason.

Chandler Carruth's Harder Line

At CppCon 2014, Google's Chandler Carruth stated: Discontiguous data structures are the root of all evil. He urged developers to "say no to linked lists" because nothing harms modern microprocessor performance more than linked-list structures. This talk became a primary source for the "linked lists are dead" meme.

Community Benchmarks

Reproductions of Stroustrup's experiment show std::list only outperforms std::vector when element size exceeds ~1 KB and element count exceeds 10,000 — the point where vector's move cost surpasses pointer-chasing cost. An extreme case: a buddy allocator implemented with std::vector allocated 1 GiB in ~2 minutes; the same logic with std::list took ~25 minutes (12× slower). In high-performance C++ circles, the rule of thumb is: if you're using std::list, you're likely wrong; 99% of cases should use std::deque or std::vector.

Linked Lists Are Not Dead — They Moved Backstage

Stroustrup himself calls the extreme "lists are evil" view absurd. Linked lists persist in critical systems:

Ubiquitous in the Linux Kernel

The kernel's intrusive list_head appears everywhere: scheduler queues, memory management, filesystems, timers. Kernel constraints favor linked lists:

Node lifetime is owned by external objects (processes, page frames, inodes) — copying is not allowed, so array-style bulk moves are impossible.

O(1) removal of arbitrary nodes is required (process kill, page reclaim).

The 16-byte prev/next pointers are not overhead but hooks embedded in the object.

Stroustrup acknowledges intrusive lists can be very fast, though he notes vectors are often smaller and faster even for insert/erase — if you truly need a list, the kernel qualifies.

Large Objects + Heavy Insert/Delete

Game engines, physics engines, scene graphs, and particle systems handle large objects where vector move cost dominates; linked lists (or custom list-based structures) remain common.

Academic Counterexample

A 2025 arXiv paper benchmarked containers under real cache hierarchies and found that for workloads with "many amortized O(1) insertions, very few traversals," replacing std::list with std::vector increased total runtime by over 30% because vector's element moves became the dominant cost. Big-O analysis isn't wrong — it just assumes negligible memory-access cost.

Modern Incarnations of Linked-List Thinking

Today's linked-list derivatives preserve logical flexibility while engineering around physical locality:

Skip Lists (Redis sorted sets): multi-level linked lists for O(log n) operations.

B-trees / B+ trees (database indexes): unrolled linked lists with high fanout, combining block locality with O(log n).

plf::colony, unrolled linked lists : pack multiple elements per node to reduce pointer chasing — a game-industry modernization.

LRU caches : hash table + doubly linked list, O(1) lookup + O(1) removal, still the industrial standard.

Chandler Carruth's CppCon 2016 follow-up talk explicitly advocates such hybrid data structures .

Synthesis: Three Half-Truths

"Linked lists are dead" — true for application-layer business code (CRUD, traversal-heavy, small elements). Default to array/deque.

"Linked lists lose to arrays" — true for performance-sensitive code where access patterns are known and data volume is large; cache-hit rate is king. Stroustrup's "default vector unless strong reason" applies.

"Linked lists moved backstage" — true system-wide: kernels, allocators, compilers, game engines, databases still rely on linked lists and their variants. They are no longer classroom stars but the "behind-the-scenes workers" supporting the software world.

The real lesson: beyond algorithmic complexity lies computer architecture; above Big-O sit cache lines, prefetchers, and the memory wall. Do not blindly trust that O(1) is faster than O(N).