Both Are O(n). One Is Far Slower.
Traversing an array and traversing a linked list are both linear. On real hardware the array can be an order of magnitude faster, because complexity counts operations and hardware charges for data movement and dependencies.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
What each structure asks the memory system for
An array of n four-byte integers occupies 4n contiguous bytes. Scanning it touches roughly 4n / lineBytes cache lines, each fully used, with a constant stride the prefetcher recognises immediately. Most iterations never wait for memory at all, because the line arrived before the loop asked for it.
A linked list of the same n integers allocates n separate nodes, each holding a value and at least one pointer. Every node is likely on its own cache line, so the scan touches roughly n lines rather than 4n/lineBytes — potentially an order of magnitude more. Worse, each line is barely used: of the bytes fetched, only the value and the pointer are read.
The layout below shows the two side by side with the same logical content. The wasted fraction in the list case is the part that never appears in complexity analysis.
This is one list node's cache line. The array line at the same size holds sixteen 4-byte integers, all of which the scan uses. The list fetches the same 64 bytes to use sixteen of them.
The dependency is worse than the cache miss
Poor cache utilisation is the visible half. The decisive half is the dependency chain. In the array loop, the address of every element is computable from the index, so the core can have many loads outstanding and overlap their latencies. In the list loop, the address of node i+1 is a value stored inside node i, so it cannot be requested until node i has arrived.
That reduces memory-level parallelism to one. Out-of-order execution cannot help, because it needs independent work and there is none. The prefetcher cannot help, because there is no address pattern to extrapolate. The loop therefore runs at approximately one full memory round trip per node, which is the mechanism developed in When You Cannot Ask the Next Question Yet.
This is why the gap is so much larger than the cache-utilisation numbers alone suggest. The array is not merely fetching fewer lines; it is fetching them *concurrently*, while the list fetches them strictly one at a time.
1sum = 02node = head3while (node != null) {4 sum += node.value5 node = node.next // address of next load lives in the current line6}7 8// cache lines touched: ~n (one per node)9// useful bytes per line: a small fraction10// outstanding misses: 111// prefetcher: cannot predict heap pointers1sum = 02for (i = 0; i < n; i++) {3 sum += arr[i] // address computed from i, known immediately4}5 6// cache lines touched: ~4n / lineBytes7// useful bytes per line: all of them8// outstanding misses: many9// prefetcher: constant stride, runs ahead of the loop10// and the loop may vectorise -- see [[auto-vectorization]]Three independent hardware advantages compound: fewer lines fetched, every fetched byte used, and accesses overlapping instead of serialising. Complexity analysis counts the loop iterations, which are identical, and is silent on all three.
When the list is still the right answer
None of this makes linked lists a mistake. It makes their advantage narrower and more specific than the complexity table suggests. A list gives O(1) insertion and removal given a reference to the position, and it gives stable references that survive mutation — an array may reallocate and invalidate every pointer into it.
The catch is that finding the position is itself a traversal, so "O(1) insertion" is often O(1) insertion after O(n) search, and the search pays every cost above. Lists win when you already hold the position: intrusive lists in kernels, LRU eviction lists where the node is reachable from a hash table, free lists in allocators, and any structure where nodes are spliced rather than searched.
The honest summary is that complexity analysis tells you how cost scales, and hardware tells you the constant factor — and when the constants differ by an order of magnitude, they decide the outcome at every practical n. Both analyses are necessary; neither is sufficient.
| Requirement | Array wins | Linked list wins |
|---|---|---|
| Sequential traversal | Decisively — locality plus parallelism | |
| Random access by index | Decisively — computed address | |
| Insertion when you already hold the position | Yes — no shifting of elements | |
| Insertion found by searching | Usually — the search dominates | |
| Stable references across mutation | Yes — nodes do not move | |
| Splicing whole sublists | Yes — pointer surgery, no copying | |
| Memory overhead per element | Lower — no pointers, no per-node allocation | |
| Vectorisation potential | Yes — contiguous and predictable | No |
Key points
- Array traversal touches far fewer cache lines and uses all of each; list traversal touches one line per node and uses a fraction.
- The decisive factor is the dependency chain: list addresses must be loaded, so accesses serialise at full memory latency.
- Prefetching, memory-level parallelism and vectorisation are all available to the array and none to the list.
- Complexity analysis is correct about scaling and silent about constant factors, which here differ by an order of magnitude.
- Lists remain right when you already hold the position, need stable references, or splice rather than search.
Progressive depth
Overview
Both take O(n) to traverse, but the array is usually much faster on real hardware because its elements sit next to each other in memory and the list's do not.
Practical
Default to contiguous structures — arrays, vectors, slices — for anything you will iterate. Reach for a linked structure when you already hold a reference to the insertion point, need references that stay valid across mutation, or splice sublists. If you find yourself searching a list to find where to insert, the search has already cost you more than the insertion saves.
Advanced
Two distinct hardware effects compound. Spatial locality means the array fetches fewer lines and uses all of each, while list nodes waste most of every line they pull in. Separately, the array's addresses are computable so many loads overlap, while the list's next address is a loaded value, capping memory-level parallelism at one. The second effect usually dominates, which is why the gap exceeds what a pure cache-utilisation calculation predicts.
Internals
The list loop is limited by the dependency chain through memory: each iteration is a load whose result feeds the next load's address generation, so the loop's minimum period is the load-to-use latency of whichever cache level the node lives in. Out-of-order execution cannot compress this because the scheduler has no independent work to fill the gap; the reorder buffer fills with instructions waiting on the same chain. Node allocation order matters too — nodes allocated consecutively may land near each other and recover some locality, which is why a freshly built list can measure much faster than one that has been mutated for hours, and why microbenchmarks of this comparison are notoriously optimistic about lists.
Loop Order & Locality
Change an input and watch which number moves — and which one refuses to.
Identical arithmetic, identical element count, identical complexity. Only the order changed. Column-major traversal of row-major storage touches a new line on essentially every access; tiling restores the reuse by keeping a block resident while it is used.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Array loop → address generation: element addresses come from the induction variable, so they are known many iterations ahead.
- 2Prefetcher → cache: the constant stride is detected and lines are fetched before the loop requests them.
- 3List loop → load: the next node's address is a field inside the current node, so it is unknown until that load returns.
- 4Load-to-use chain → stall: the core has no independent memory work to overlap, so each iteration waits a full access latency.
- 5Allocation scatter → cache lines: nodes allocated at different times land on different lines, so each node costs a line whose remaining bytes are discarded.
- • "Same complexity, so pick either." Complexity describes scaling; the constant factor here differs by roughly an order of magnitude and decides the outcome.
- • "My benchmark shows the list is fine." Freshly allocated nodes are often contiguous by accident. Fragment the heap first and measure again.
- • "Adding a prefetch hint will fix the list." The prefetcher fails because the address is unknown, not because it was not asked.
Consequences, controls and cost
- • Iteration-heavy workloads on linked structures run far slower than their complexity suggests, often by an order of magnitude.
- • Replacing a list with a vector is frequently a large speedup with no algorithmic change whatsoever.
- • Benchmarks built on freshly allocated lists overstate list performance, because allocation order accidentally supplies locality that real usage destroys.
- • Default to contiguous storage for anything iterated, and treat a linked structure as the exception requiring justification.
- • Where a list is genuinely needed, allocate nodes from a pool or arena so they stay near each other in memory.
- • Keep the payload in a contiguous array and use the list only for ordering, so traversal touches dense data.
- • If the position is always found by searching, the list's O(1) insertion is not being used — reconsider the structure.
- • Traverse the same payload as an array and as a list, counting cache misses and cycles rather than just wall time.
- • Build the list with interleaved unrelated allocations to destroy accidental contiguity, then re-measure — the gap usually widens sharply.
- • Check memory-level parallelism: the array loop should show many outstanding misses, the list loop approximately one.
- • Contiguous storage costs O(n) insertion in the middle and invalidates references on reallocation.
- • Pooling list nodes recovers locality but complicates lifetime management and can waste memory on unused pool capacity.
Scope
§224 — what these claims are specific to.
- GENERALThe mechanism holds on any machine with caches and prefetching, which is all current general-purpose hardware. The size of the gap is MICROARCH-SPECIFIC and grows with the CPU-to-memory latency ratio.