Is the prev pointer worth its memory across 10 million nodes, and what do you lose without it?

## Price the field before arguing about it A `prev` reference is one pointer-sized field per node. On a 64-bit machine that is 8 bytes; across 10^7 nodes it is about 80 MB of pure bookkeeping, before the payload. Whether 80 MB is a rounding error or the whole argument depends on the ceiling: on a fleet of instances sized to a fixed memory limit per process, it can be the difference between fitting the working set and not, and it is multiplied by every replica. The right first move in the interview is to compute it out loud rather than to reason about it qualitatively. Three caveats keep the estimate honest. First, the *relative* cost depends on the node's payload — for a node holding a value and a `next`, adding `prev` grows it by half; for a node holding a fat record, the extra field is noise. Second, per-node allocation overhead may already dwarf the field, in which case the marginal decision is smaller than it looks. Third, if the structure is dense and long-lived, nodes can be held in a preallocated block and linked by integer indices rather than references, which shrinks both link fields to 4 bytes and makes the `prev` question cheaper on both sides. ## What the field actually buys Be precise, because the usual answer over-claims: - **O(1) unlink of a held node.** Removing a node means writing its predecessor's `next`; `prev` names that predecessor in one hop. - **O(1) insert before a held node** — same reason. - **O(1) delete-last given a tail reference**, via `tail.prev`. - **Backward iteration at O(1) per step.** And what it does not buy: nothing about *finding* a node. Deletion by value stays O(n) in both variants, because the scan dominates. If your workload's deletes are value-driven, `prev` changes the constant factor and nothing else — that alone can settle the question. ## The case where a trailing reference wins outright A large fraction of real deletions happen during a sweep the code already performs: walk the list, drop the entries that match a predicate, keep the rest. In that shape you do not need `prev` stored in every node, because the traversal *is* the predecessor: carry a second reference one step behind the cursor, and unlinking the current node is one write. Zero extra bytes per node, constant-time removal, and the pattern generalises to any single-pass filter, compaction or expiry scan. The catch is a real one. The trailing reference is NIL while the cursor is on the first node, so removing the head is a separate branch that updates the list's handle instead of a node's field. That branch is where the bugs live, and it is worth naming in an interview: you are trading 80 MB against a special case that every future maintainer of that loop has to re-derive. ## The cases where a trailing reference cannot help Draw the line clearly: 1. **Node references arriving from outside the list.** If a separate index maps keys to nodes so callers can remove arbitrary elements in constant time, there is no traversal in flight and no trailing reference to have. Without `prev`, every such removal degenerates to an O(n) walk, and the index's whole purpose evaporates. 2. **Backward movement as a user-visible operation.** A media player's previous-track control steps backwards from wherever the cursor sits. Without `prev` each step is a re-walk from the head, so a listener tapping back repeatedly pays a full traversal each time — asymptotically catastrophic on a long queue and easy to observe as input lag. 3. **Insert-before at a held position**, for the same reason as unlink. If any of these is on the critical path, the field is not overhead; it is the feature. ## Making the call The decision procedure worth stating: enumerate the operations on the hot path and their frequencies; check whether every removal can be co-located with a traversal you already run; price the field against the actual ceiling rather than against intuition; and only then weigh the maintenance cost of the trickier idiom. If the memory is comfortable, keep `prev` — the code is simpler, the failure modes are fewer, and the operation set is strictly larger. If the ceiling is genuinely binding and the access pattern is sweep-shaped, drop it, and put the head-node branch behind one reviewed helper rather than open-coding it at every call site. Two further points a lead should own. **Reversibility:** dropping `prev` is easy to undo in code but hard to undo in an API — once callers hold node handles and expect constant-time removal, adding the field back is a data migration on a live structure, not a patch. Design for the operation set you will plausibly need, not the one you have this quarter. **Scale honesty:** if 10^7 nodes are actually being scanned, the variant choice may be the second-order question. The memory ceiling that makes `prev` unaffordable is often the same ceiling that argues for an index or a different representation entirely, and a lead is expected to say so rather than optimise a field within a structure that no longer fits the workload.