In a doubly-linked list, why is deleting a node you already hold O(1) but O(n) in a singly-linked list?
answer
- Who has to stop pointing at the victim?
- Which neighbour's field must change?
- Can the node name its predecessor?
- Holding the node is a precondition
- Delete by value is search-dominated
basics
~20 sUnlinking a node means rewriting its predecessor's next reference. A doubly-linked node stores prev, so both neighbours are one hop away — O(1). A singly-linked node cannot look backwards, so its predecessor must be found by walking from the head.
solid answer
~40 sRemoving a node from a chain requires making its predecessor point past it. That is the whole difference. A doubly-linked node names both neighbours, so the unlink is a fixed handful of writes: `x.prev.next = x.next` and `x.next.prev = x.prev`, plus the boundary cases where one side is NIL. A singly-linked node names only its successor, so the predecessor whose field must change is unreachable from the node itself — you re-walk from the head, O(n). The same asymmetry governs *insert before* a held node. The trap is stating it as "doubly-linked delete is O(1)": that holds only when the node reference is already in hand, for example handed back by an external index. Deleting *by value* is O(n) in both variants, because the search dominates and the rewiring is noise.
code
pseudocode · 14 linesDELETE-NODE(list, x) // x is already held
if x.prev == NIL
list.head = x.next // x was first
else
x.prev.next = x.next
if x.next == NIL
list.tail = x.prev // x was last
else
x.next.prev = x.prev
x.prev = NIL // do not keep pointing
x.next = NIL // into the live list
list.size = list.size - 1go deeper
Be ready to say that removing a node means making its predecessor point past it, and that a singly-linked node cannot reach its predecessor while a doubly-linked one can.
Explain the unlink write-by-write, including the branches for a missing neighbour at either end, and state the precondition out loud: the O(1) holds only when the node reference is already in hand.
Demonstrate the production judgment: know where held node references actually come from, why deletion by value stays linear, and why a removed node's own fields should be cleared rather than left pointing into the live chain.
Own the tradeoff between exposing node handles from an API — which is what makes O(1) unlink usable at all — and the encapsulation and lifetime problems those handles create for every caller that stores one.
## What deletion actually requires A linked list is defined by the reference fields pointing *into* each node. To remove node `x` from the chain, nothing about `x` matters except that whoever points at `x` must be made to point at `x`'s successor instead. So the real question for every variant is: **can I name the node that points at me, and how fast?** - **Doubly-linked:** yes, in one hop — that is precisely what `prev` is for. - **Singly-linked:** no. References run one way. The predecessor exists but is not addressable from `x`, so it must be rediscovered by starting at the head and walking until you find the node whose `next` is `x`. That is O(n). The unlink itself is a constant number of field writes in both cases. The cost difference is entirely the search for the predecessor. ## The boundary cases the O(1) claim hides "Two writes and you're done" is the happy path. A correct unlink in a doubly-linked list branches on whether either neighbour is missing: if `x.prev` is NIL then `x` was first and the list's head reference must move; if `x.next` is NIL then `x` was last and the tail reference must move. Both branches are still constant work, so the bound holds, but a candidate who cannot name them has memorised the two-line version rather than reasoned about it. Clearing `x`'s own fields afterwards matters too — a removed node still pointing into the live list keeps that whole suffix reachable from any stale reference, which is a memory-retention bug in a managed environment and a dangling-reference hazard in a manual one. ## "Doubly-linked delete is O(1)" — the direction of the claim The bound is conditional on *already holding the node*, and it is worth being explicit about where such a reference comes from. Typical sources are a cursor that is mid-traversal, a handle returned when the element was inserted, or a separate index structure mapping keys to nodes. In all of those, the node arrives from outside the list and the O(1) unlink is real and valuable. What the bound never promises is *delete by value*. `remove(v)` on a doubly-linked list is O(n): the list has no positional or key-based lookup, so finding the node dominates and the constant-time unlink at the end is invisible in the total. A candidate who answers "O(1)" to "what does removing a value from a doubly-linked list cost?" has generalised the wrong half of the operation. ## Insert-before, and the other things `prev` buys The same argument covers inserting *before* a held node — it also requires writing the predecessor's `next` field, so it is O(1) with `prev` and O(n) without. Inserting *after* a held node is O(1) in both variants, which makes a nice check question: nothing about that operation looks backwards. Beyond unlink and insert-before, `prev` buys backward traversal. Consider a media player holding its play queue as a list of track records: "next track" needs only `next`, but a "previous track" control needs to step backwards from wherever the cursor currently sits, repeatedly and cheaply. With a singly-linked queue, each backward step is an O(n) re-walk from the head, so a listener tapping back five times pays five full traversals. That, more than the delete cost, is usually what settles the variant choice for navigation-shaped workloads. ## The singly-linked trick, and why it is not a general answer There is a well-known dodge for deleting a held node `x` from a singly-linked list in constant time: copy `x.next`'s value into `x`, then unlink `x.next` instead. The chain ends up one node shorter with the right sequence of values, and no predecessor was needed. It has two hard limits, and being able to state them is what separates a memorised trick from understanding: 1. **It cannot delete the last node.** There is no successor to copy from, and the last node's predecessor still needs its `next` set to NIL — the exact thing you cannot reach. 2. **It invalidates outside references.** The node object that survives is `x`, now impersonating its successor, while the *successor's* node object is the one physically removed. Anything else holding a reference to the successor — an index, a cursor, another data structure — is now pointing at a node that has silently left the list. The values are right; the identities are not. Use it in a self-contained chain where no one else holds node references, and never where node identity is externally meaningful. ## Interview shape State the predecessor requirement first, then the variant answer, then volunteer the qualifier that the O(1) applies to the unlink given the node, not to removal by value. That last sentence is usually the one being fished for.
- So what does removing a value from a doubly-linked list cost?O(n). The list offers no lookup by key or position, so the node must be found by scanning from an end. The unlink is O(1) once you are there, but the search dominates. The constant-time claim only applies when something else — a cursor or an external index — already hands you the node.
- Besides O(1) unlink, what else does the prev reference buy?Backward traversal at O(1) per step, which is what a previous-track or step-back control needs; inserting *before* a held node in O(1); and, with a tail reference, deleting the last node in O(1) via `tail.prev`. Inserting *after* a held node is O(1) in both variants — that one is not a doubly-linked advantage.
- Can you ever delete a held node from a singly-linked list in O(1)?Yes, by copying the successor's value into the held node and unlinking the successor instead. It fails on the last node, since there is no successor to copy, and it silently invalidates any outside reference to the successor node, which is the object actually removed. Safe only when no one else holds node references.
saying these in an interview costs you the question
- Says doubly-linked deletion is O(1) with no held-node precondition
- Answers O(1) for removing a value from a doubly-linked list
- Thinks the singly-linked cost comes from rewiring, not from finding the predecessor
- Claims inserting after a held node needs the prev reference
- Forgets the head and tail cases when a neighbour is NIL
- Presents the copy-the-successor trick without its last-node and identity caveats