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.