Why does traversal of a long-lived linked list slow down as its nodes get scattered?

## The symptom A service walks a chain of records on every request. The code has not changed, the element count is flat, and the profile shows the same function doing the same number of iterations — yet the pass that took a few milliseconds after a restart takes several times that after weeks of uptime, and a redeploy silently "fixes" it until it drifts back. This is one of the few performance mysteries where big-O is not merely unhelpful but actively misleading: the complexity is identical before and after. ## Why a fresh chain is fast When a chain is built in one burst, its nodes are allocated back to back. Most allocators satisfy a run of same-sized requests from adjacent space, so consecutive nodes often land close together. Following links then walks memory roughly in address order, and each memory transfer brings along neighbours that the next few hops will want. The traversal behaves almost like a scan of contiguous storage — which is exactly why a benchmark written right after building the structure reports a flattering number. ## Why a churned chain is slow Now run for weeks. Nodes are removed and added; unrelated allocations of other sizes come and go between them; freed blocks are reused by whatever asked next. The surviving nodes end up at addresses that have nothing to do with their order in the chain. Two consequences stack: 1. **Each hop is likely to touch memory nothing has recently brought in.** The neighbours fetched alongside a node are now other objects, not the next node. 2. **The hops cannot overlap.** This is the part people miss. The address of node k+1 lives *inside* node k, so the machine literally does not know what to fetch next until the current fetch completes. Independent reads can be issued together and their latencies hidden behind one another; a pointer chase cannot. The costs add rather than overlap, and a chain of a million dependent misses is a chain of a million latencies laid end to end. That is the whole mechanism: the algorithm's operation *count* is unchanged, and the operation *price* has gone up several-fold. ## Confirming it rather than guessing The diagnosis has to distinguish "layout" from the ordinary suspects, and there is a clean experiment: - **Rebuild and re-time.** Copy the elements, in order, into a newly allocated chain and run the identical traversal over it. Same length, same code, same data. If the fresh copy is markedly faster, the difference is where the nodes sit — nothing else varies. - **Rule out the boring causes first.** Confirm the element count really is flat (a slow leak into the structure explains the symptom trivially), confirm the per-iteration work has not changed, and confirm the process is not simply under memory pressure for unrelated reasons. - **Look at the shape of the slowdown.** Layout decay is gradual and resets on restart. A step change at a deploy points at code; a sawtooth tied to a periodic job points at that job. ## What to do about it The fixes follow from the mechanism: - **Periodic compaction.** Rebuild the chain into freshly allocated nodes in traversal order during a maintenance window. It restores the fast case and buys the same amount of time again. - **Allocate nodes from a dedicated region.** If every node comes out of one reserved area used for nothing else, hops stay near each other by construction, and reuse within that region keeps them there. The price is managing that region's lifetime and its fragmentation. - **Store the payload inline, not behind another reference.** A node holding a reference to its value turns one dependent hop into two, doubling exactly the cost that is hurting. - **Make fewer hops per unit of work.** A node carrying a small block of elements amortizes one dependent access across many values, which attacks the problem at its root. One caution about the general lesson: this is not "pointer structures are slow". It is that their traversal cost is a function of *history*, not just of size — a property that no complexity annotation records, and one that only shows up after something has been running long enough for its allocations to interleave with everything else. ## The interview answer Say the three things in order: the complexity did not change, the per-hop cost did, and the reason the hops cannot be overlapped is that each address is stored in the node before it. Then name the experiment — a freshly rebuilt copy timed against the live structure — because at senior level the diagnosis method matters as much as the explanation.