For a linked list node you already hold, when is O(1) removal true and when is it a lie?

### The claim under test "Linked lists remove in O(1) if you already have the node" is repeated so often that it is worth taking apart precisely, because it is true, false, or partly true depending on a single design decision: whether nodes carry back-links. ### Where it is true In a doubly linked list, each node stores references to both neighbours. Removing a node you hold is: ``` node.prev.next = node.next node.next.prev = node.prev ``` plus a branch for the ends, where one of the neighbours is absent and the container's head or last reference must be reassigned instead. No search, fixed work, any position — genuinely O(1). This is the property that makes doubly linked lists the backbone of eviction orders, ready queues and anything where an arbitrary element must leave the middle in bounded time. It is not free. The costs, in the order a reviewer should raise them: - **Memory.** One extra reference per node. On a node whose payload is a couple of words, back-links can be a double-digit percentage of the structure's footprint, multiplied across every node on every machine running the service. - **A second invariant.** Every insert and every remove writes two links instead of one, and there are twice as many ways to leave the chain half-updated. Corruption is also worse: a broken forward link truncates, whereas an inconsistent pair can produce a chain that walks correctly in one direction and not the other. - **Cache behaviour.** Fatter nodes mean fewer per cache line, so traversal-heavy workloads pay for a removal-path optimisation they may not use. ### Where it is a lie In a singly linked list the node hands you nothing about who points at it. Removal requires a write into the predecessor, and reaching the predecessor from a forward-only node means walking from the head: O(n). Two partial escapes exist and both have sharp edges. Copying the successor's payload backwards and splicing the successor out is O(1), but it cannot touch the last node and it invalidates anyone else's reference to the successor. A separate index from identifiers to *predecessor* nodes restores O(1) removal, but it must be updated on every insert and every removal, which is a second structure to keep consistent and usually more expensive than back-links would have been. So the precise statement is: **constant-time removal of an arbitrary held node is a property you buy with back-links or an equivalent index; it is not a property of chained nodes as such.** ### The scheduler decision Concretely: a scheduler keeps pending jobs on a run list, and the cancellation path must stay within a tight latency budget while the list can be large. Three defensible designs: | Design | Cancel cost | Memory | Failure to watch | | --- | --- | --- | --- | | Back-links on every node | O(1), any position | +1 reference per node, always paid | Two links to keep consistent per splice | | Forward-only, search on cancel | O(n) | Minimal | Cancel latency scales with queue depth | | Forward-only, dead flag + reaping pass | O(1), any position | Dead nodes held until reaped | Unbounded growth without a reaping policy | The decision turns on numbers you should ask for out loud: how many nodes are live, how often cancellation happens versus traversal, and whether the memory or the tail latency is the tighter constraint. A short queue with rare cancellations does not justify back-links — the O(n) search is a walk over a handful of nodes and the simpler structure is worth more than the asymptotics. A large queue on the cancel hot path does justify them, and the reviewer should expect the extra per-node cost to appear in the memory estimate rather than be discovered later. The dead-flag option is the interesting middle. Cancellation becomes a single field write, correct at every position including the last, and node identity is preserved for anyone holding a handle. What it defers is real: dead nodes occupy memory and are still visited by every traversal until something unlinks them. That makes the reaping policy part of the design, not an implementation detail — who sweeps, how often, and what bounds the dead fraction. A cancel-heavy workload with no reaping turns a list of pending jobs into a list of mostly-cancelled jobs, and dispatch slows in proportion. ### What a strong answer sounds like Refuse the slogan, name the dependency (back-links), state both costs of buying it, name the two singly-linked escapes and their limits, and then choose against the workload's actual numbers rather than against the asymptotics alone. The candidates who fail this question are the ones who answer "O(1)" and stop.