Linked Lists Dead? Why O(1) Isn't Always Faster Than O(N) — Stroustrup's Insight

Linked Lists Were Once the Star

In university data structures courses, a classic rule is taught: arrays excel at queries, linked lists excel at insertions. Array insertion/deletion requires shifting elements (O(n)), while linked lists only adjust pointers (O(1)). In pure algorithmic analysis, this conclusion seems indisputable.

However, this conclusion rests on a hidden premise: it assumes memory access is free, counting only basic operation counts.

The Memory Wall and Caches

Over decades, CPU compute speed has grown exponentially while DRAM latency has improved minimally, creating a Memory Wall. A modern desktop CPU accesses L1 cache in a few cycles, but a main memory access may cost hundreds of cycles.

To bridge this gap, CPUs insert multi-level caches (L1/L2/L3) with two key mechanisms:

Cache line prefetch: CPUs load data in ~64-byte cache lines, not bytes. Accessing one int brings neighboring ints into cache.

Hardware prefetchers: If access addresses are linearly increasing, the CPU preloads subsequent data.

This underpins the Locality Principle. Data that is spatially adjacent and temporally close is favored by modern CPUs. Performance largely depends on how close data is to the core; cache misses occur when needed data is far away.

Linked lists violate both principles:

Nodes are scattered across the heap; each pointer hop can cause a cache miss.

Traversal requires reading a pointer before knowing the next node's address, defeating hardware prefetchers — a pattern called pointer chasing.

Array insertion's element shifting uses memcpy, which is contiguous and prefetch-friendly, making it surprisingly fast. Linked list insertion's pointer changes sound cheap, but the pointer-chasing journey to the insertion point may incur hundreds of cache misses.

Big O says linked lists win; CPU caches say linked lists lose. The real judge is actual measured time.

Experts' Verdicts

Bjarne Stroustrup, at the 2012 Going Native keynote, presented a classic experiment (from Jon Bentley): insert random integers in sorted order, then delete at random positions — linked list or array? The result was counterintuitive: std::list was crushed by std::vector, even though the workload appeared to favor linked lists.

Stroustrup later clarified on isocpp.org:

My point was never about linked lists per se. Linked lists have their uses, but this example isn't one of them. Note my conclusion mentions neither list nor vector.

He emphasized three principles:

don't store data unnecessarily keep data compact access memory in a predictable manner I stress the importance of cache effects. My experience is that almost everyone forgets this when discussing algorithms.

His practical advice: default to std::vector. More generally, use contiguous memory representations unless there's a compelling reason not to.

Chandler Carruth (Google LLVM lead, C++ committee member) was even blunter at CppCon 2014: Discontiguous data structures are the root of all evil. He urged:

Please say no to linked lists. There is almost nothing more harmful you can do to the performance of an actual modern microprocessor than to use a linked list data structure.

Community Benchmarks: How Bad Is It?

Developers reproducing Stroustrup's experiment found that std::list only begins to outperform std::vector when element size exceeds 1 KB and element count surpasses 10,000 — because only then does vector's data-moving cost exceed pointer-chasing cost.

An extreme case from a buddy allocator teaching project: allocating 1 GiB with std::vector took ~2 minutes; with std::list it took ~25 minutes — over 12x slower.

In high-performance C++ circles, a rule of thumb emerged:

if you're using std::list, you're probably using it wrong; 99% of the time you should use std::deque or std::vector

.

Are Linked Lists Really Dead?

Stroustrup himself rejects the extreme "linked lists are evil" view: Obviously, that's absurd. Linked lists haven't died; they've just changed how they live.

Linked Lists Are Everywhere

Open the Linux kernel source, and the intrusive doubly-linked list list_head appears everywhere: process scheduling queues, memory management, filesystems, timers — nearly every subsystem uses it.

Why does the kernel love linked lists? Kernel constraints include:

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

O(1) removal of arbitrary nodes is required — a process can be killed, a page frame reclaimed at any moment.

The 16 bytes of prev/next pointers in each node aren't overhead; they're hooks embedded in the object itself.

Stroustrup acknowledges in his FAQ that intrusive lists can be very fast, though

a vector is more compact and is therefore smaller and faster in many cases — even when you do inserts and erases

, provided you actually need a list. In the kernel, that condition holds.

Linked Lists Still Have Uses

When element size exceeds 1 KB and counts are huge, vector's move cost lets linked lists win. Game engines, physics engines, scene graphs, and particle systems handle such large objects; linked lists (or custom list-based structures) remain common. Large objects + intensive insert/delete = linked lists can still win.

A 2025 arXiv paper benchmarking containers on real CPU cache hierarchies found that in workloads with heavy amortized O(1) insertion and minimal traversal, replacing std::list with std::vector increased total runtime by over 30%, because linked lists provide true O(1) pointer operations while vector's moves became the dominant cost.

Big O analysis isn't wrong; it's just accurate only when memory access cost is negligible.

New Forms of Linked Lists

Today's linked lists aren't the textbook "one data field plus one pointer" anymore. The idea lives in modern structures:

Skip Lists: Core of Redis sorted sets, using multi-level lists for O(log n).

Unrolled linked lists / B-trees / B+ trees: Database indexes pack multiple elements per node (high fanout), combining block locality with O(log n).

plf::colony, unrolled linked lists: Game industry's "modernized" linked lists, packing multiple elements per node to reduce pointer chasing.

LRU Caches: Hash table + doubly-linked list remains the industrial standard for O(1) lookup + O(1) eviction.

These structures inherit linked lists' logical flexibility while using engineering techniques to fix their physical locality problems. Carruth's CppCon 2016 follow-up talk covered exactly this Hybrid Data Structures design philosophy.

Conclusion

The three opening viewpoints are each half right:

Linked lists are dead — true for application-layer business code. In most CRUD, traversal-heavy, small-element scenarios, blindly choosing arrays (or deque) is almost always correct. Carruth's words target this default scenario.

Linked lists lost to arrays — true for performance-sensitive contexts. When access patterns are known and data scales, cache hit rate is the lifeline; contiguous memory is king. Even Stroustrup advises default vector, unless there's a good reason.

Linked lists moved backstage — true for the full system picture. Deep in kernels, allocators, compilers, game engines, databases, linked lists (and variants) still run elegantly. They're no longer classroom stars, but the behind-the-scenes workers supporting the software world.

The real lesson isn't "linked lists vs arrays" but that

beyond algorithmic complexity analysis, there's a course called Computer Architecture; above Big O notation stand cache lines, prefetchers, and the memory wall

. Don't blindly believe O(1) is always faster than O(N).