In an order book where cancels hold a node handle, what does a linked list guarantee that a compacted array does not?

## Position versus identity Every container answers "which element do you mean?" in one of two ways. An array answers by **position** — the third slot — and position is a property of the current layout. A linked structure answers by **identity** — this node — and identity is a property of the element itself. The distinction is invisible until the container mutates, and then it decides whether a stale reference is safe, wrong, or detectably wrong. ## The workload An order book holds resting orders, grouped by price level and kept in arrival order within a level so that matching is fair. Three things happen constantly: new orders rest, orders at the front execute and leave, and orders anywhere in the middle are cancelled by their owner. The cancel path is the interesting one. It arrives with a client-supplied identifier, and the book must find that specific order and remove it, ideally without scanning the level — cancels are frequent and latency-sensitive. So the book keeps, somewhere, a mapping from client identifier to "where the order lives". The question is what "where" can safely be. ## Why an index is not an answer Suppose the level is a contiguous array and "where" is an index. - **Removal plus compaction.** When an order in the middle leaves, the elements after it are slid down to keep the level contiguous. Every stored index above the removed slot is now off by one and refers to a neighbouring order. Nothing errors; the next cancel simply removes the wrong order. - **Growth.** When the level exceeds capacity, the whole block is relocated. Indices still point at the right logical positions, but any raw pointer taken into the block is dangling. - **Tombstones instead.** You can refuse to compact and leave holes, which keeps indices stable — but now the level accumulates dead slots, scans get slower, and you need a reclamation strategy. This is the beginning of a real design, not a refutation. The failure mode that matters is the first one: it is *silent*. A dangling pointer usually crashes; a shifted index produces a plausible, wrong action. In a book, that is a cancelled order that the client never cancelled. ## What the list guarantees In a doubly linked level, a node's address is fixed for its whole life. Inserting elsewhere in the level rewrites two links between existing nodes; it does not touch the handle you hold or the node it points at. Removing some other order likewise touches only that order's neighbours. So: - **The handle survives arbitrary unrelated mutation.** No versioning, no fix-ups, no re-lookup. - **Cancel is constant time end to end.** The handle is the location, so there is no search; the unlink is a fixed number of pointer writes, and the order's neighbours close around it. - **Order within the level is preserved exactly.** Removing from the middle changes nobody else's relative position, which is the fairness property the book has to maintain. ## What it costs, and the mature alternative The list buys stability with locality. Walking a price level chases pointers instead of striding through contiguous memory, so scans prefetch poorly. The standard mitigation is to allocate all nodes from one contiguous arena rather than individually, which restores much of the locality and, as a bonus, makes node allocation a bump or a free-list pop instead of a general-purpose request. The genuinely mature answer is that the property is separable from the structure. You can build stable handles over an array: never compact, allocate slots from a free list of vacated slots, and store a **generation counter** in each slot that increments on reuse. A handle is then (slot, generation); on cancel you compare generations, and a stale handle is *detected* rather than silently misapplied. You keep contiguous storage and locality, you pay one comparison and some permanently reserved slots, and you have converted a silent wrong-order bug into an explicit "already gone" response. That last conversion — from silent corruption to a checkable error — is usually the strongest argument in the room. When does the list still win? When the elements must be members of more than one collection at once (an order threaded into both its price level and its owner's list, with links embedded in the order itself), when relocation is not permitted at all because other subsystems hold raw references, or when the constant-time splice of a whole run between collections matters. ## How to answer it Name the property first — stable identity under unrelated mutation — then show the failure mode of the index version, then price both sides and offer the generation-tagged slot design as the alternative. A candidate who only says "linked lists have O(1) deletion" has answered a different, easier question.