Why is unlinking a node you already hold in a doubly linked list O(1), but O(n) in a singly linked one?
answer
- ask what the node already knows
- removal must patch the predecessor
- one link versus two links
- singly linked: walk to find the predecessor
- two pointer writes, zero traversal
basics
~20 sA doubly linked node stores a pointer to its predecessor, so unlinking it is two pointer writes. A singly linked node stores no back pointer, so the predecessor must be found by walking from the front — O(n) — before the splice can happen.
solid answer
~40 sRemoving a node means repairing the chain around it: the predecessor's forward pointer must skip over it. In a doubly linked list the node itself carries `prev` and `next`, so both neighbours are already in hand and the repair is a fixed number of pointer writes — O(1), no traversal, and nothing after the node moves. In a singly linked list the node knows only its successor, so the predecessor has to be located by walking from the front, which is O(n) even though the splice itself is still two writes. The cost difference is entirely about what the node already knows, not about how much data is copied. Note the precondition: this O(1) only applies when something else already handed you the node — searching for it by value is O(n) either way.
code
pseudocode · 12 lines// doubly linked list with sentinel head and tail nodes,
// so a live node's prev and next are never NIL
UNLINK(x) // x is a handle to a live node
x.prev.next = x.next
x.next.prev = x.prev
x.prev = NIL
x.next = NIL
// constant work: no traversal, nothing shifts
// singly linked: x.prev does not exist, so the predecessor
// must be located by walking from the front -- O(n)go deeper
Be ready to state the difference in one breath: the doubly linked node knows its predecessor, the singly linked one does not, and repairing the chain needs the predecessor. Say the precondition out loud — you must already hold the node.
Explain the exact pointer writes and why nothing else moves, then contrast with an array where interior removal shifts every later element. Mention sentinels as the reason production unlink code has no null checks.
Show you know where the handle comes from in real code and who is responsible for keeping it valid, and be able to price the back pointer: one extra word per node plus an invariant that mutations must maintain in both directions or silently corrupt.
Own the framing that the constant-time claim is a statement about identity and locality of change, not about speed. Decide when that property is worth the per-node memory and the extra invariant across a codebase other people maintain.
## What the question is really about The claim "linked lists delete in O(1)" is one of the most repeated half-truths in interviews. It is true only under a precondition — you must already be holding the node — and, for the general case, only for a doubly linked list. Understanding exactly which pointer is missing in the singly linked case is the whole answer. ## The two shapes A **node** is a small record holding an element plus one or more links to other nodes. A **singly linked** node holds one link, `next`, pointing at its successor; the list is entered at a `head` and walked forward. A **doubly linked** node holds two, `prev` and `next`, so from any node both neighbours are reachable in one step. A **handle** (or node reference) is a direct pointer to one node, held by something outside the list — a caller, an index, another data structure. Holding a handle means you skipped the search. ## The removal itself Unlinking node `x` means restoring the invariant "every live node's `next` points at the next live node". The predecessor's `next` must be redirected past `x`, and (in the doubly linked case) the successor's `prev` must be redirected back past `x`. That is a constant number of writes — two, plus optional cleanup of `x`'s own links. Crucially, **nothing else moves**: no elements are shifted, no memory is copied, and every other node keeps its address. This is the sharpest contrast with an array, where removing an interior element means sliding everything after it down one slot. So the splice is O(1) in both list shapes. The asymmetry is in *reaching the predecessor*: - **Doubly linked**: `x.prev` is right there. Total cost O(1). - **Singly linked**: nothing in `x` points backward. The only way to find the predecessor is to start at the head and walk until you find the node whose `next` is `x`. That walk is O(n), and it dominates. ## Sentinels Production doubly linked lists usually allocate two permanent dummy nodes, a **sentinel head** and a **sentinel tail**, that hold no element and are never removed. Every real node then has a real predecessor and a real successor, so the unlink code has no null checks and no special case for the first or last element. The cost is two extra nodes and the discipline of never handing a sentinel out as a handle. ## What the back pointer buys, and what it costs The extra link is what makes two operations constant-time: **unlink-by-handle**, as above, and **move-to-front** — detach a node from wherever it sits and re-attach it just after the head, again a fixed number of pointer writes, no traversal, and the node keeps its identity throughout. That second operation is why access-ordered structures are usually built on doubly linked lists. The price is real and worth stating in an interview: one extra pointer of memory per node, and a stricter invariant. Every mutation must keep both directions consistent; a forward chain that is correct while the backward chain is stale is a classic corruption bug that traversal in one direction will not reveal. A singly linked list has half the invariant to maintain and less memory per node, and it is entirely sufficient when you only ever insert or remove at the front, or only ever traverse forward. ## The trap answer A weak candidate says "linked lists have O(1) insertion and deletion" and stops. Ask them to delete a given *value* and the answer collapses: the search is O(n), so end-to-end deletion by value is O(n) in every list. The O(1) claim is a statement about the splice, and it only becomes a statement about the whole operation when an external structure already supplies the handle. Making that precondition explicit — "O(1) *given a handle*, and something else has to give me that handle" — is what separates a memorised row in a complexity table from actual understanding. ## Why interviewers keep asking it The question is a cheap probe for two different confusions at once: importing array intuition into a list ("the elements after it shift"), and dropping the precondition ("deletion is O(1)"). Both are common, both are correctable in one sentence, and how a candidate states the precondition tells you whether they have used the structure or only read about it.
- If unlinking is O(1), why is deleting a given value from a linked list still O(n)?Because finding the node dominates. The O(1) bound describes the splice only; locating the node that holds the value means walking the chain, which is O(n) in both list shapes. End-to-end deletion is O(1) only when some other structure already hands you the handle, so the search never happens.
- What does a singly linked list buy in exchange for that O(n) removal?One less pointer per node, which matters when nodes are small and numerous, and a much simpler invariant — only the forward chain can go wrong, so there are fewer ways to corrupt it. It is enough whenever you only push and pop at the front or traverse forward.
- How do sentinel head and tail nodes change the unlink code?They remove every special case. With sentinels each live node always has a real predecessor and successor, so unlinking is two unconditional writes instead of branches for the first and last node. The cost is two permanently allocated nodes that hold no element and must never be handed out as handles.
In a line of people holding hands, someone who can see both neighbours can step out instantly. If they can only see forward, someone has to walk the whole line to find who was standing behind them.
saying these in an interview costs you the question
- Claims deletion from any linked list is O(1), unconditionally
- Forgets the precondition that you already hold the node
- Thinks the elements after the removed node shift up
- Ignores the extra pointer of memory per node
- Cannot say which neighbour's link actually needs patching