Why does removing a node from a singly linked list need the predecessor, and what does that cost?
answer
- who is holding on to the node?
- a node cannot see backwards
- the link you must edit is not yours
- walk from the head one reference behind
- splice is O(1), the search is not
basics
~20 sA singly linked node stores only a forward link, so nothing inside it can change what points at it. Removal means rewriting the predecessor's link to skip the node, and locating that predecessor from the head costs O(n).
solid answer
~40 sIn a singly linked list every node knows its successor and nothing else, so the node itself is powerless to remove itself — the only reference that keeps it in the chain lives in the node before it. The removal is the single write `prev.next = curr.next`, which is O(1) once you hold `prev`. Getting `prev` is the expensive part: starting from the head you walk forward carrying a trailing reference, which is O(n) in the length of the list. So "linked lists delete in O(1)" is only true when the predecessor is already in your hand; removal *by value* or *by position* is O(n) because of the search, not because of the splice. The one shape without a predecessor is the first node, where you reassign the list's head reference instead.
code
pseudocode · 11 linesprev = nil
curr = head
while curr != nil and curr.id != target:
prev = curr
curr = curr.next
if curr == nil:
return // not present
if prev == nil:
head = curr.next // removing the first node
else:
prev.next = curr.next // the splice: one write into prevgo deeper
Be ready to say, in one breath, that removal rewrites the predecessor's forward link and that finding that predecessor from the head is the O(n) part. Then handle a two-node list on the spot.
Explain the mechanics precisely: which reference is written, why a cursor reassignment writes nothing into the structure, and why setting the node's own forward link to nil truncates rather than removes.
Show you separate the splice from the search when costing real code. A removal-by-identifier inside a loop over m targets is O(n*m) unless the pass is restructured, and that is the kind of thing a review should catch.
Own the framing that O(1) arbitrary removal is bought, not inherited: back-links cost memory per node on every node in the fleet and a second invariant to maintain. Decide whether the workload's removal rate justifies that.
### What a singly linked node actually knows A node in a singly linked list holds a payload and one forward reference to the next node. That is the entire vocabulary. Crucially, a node has no idea who points *at* it: membership in the list is expressed by somebody else's reference, and that somebody is the predecessor. This asymmetry is the whole story of deletion, and it is why deletion in a singly linked list is a fundamentally different operation from insertion after a node you already hold. ### The splice itself Suppose the chain is `prev -> curr -> rest`. Removing `curr` means making `prev` point past it: ``` prev.next = curr.next ``` One write. After it, nothing reachable from the head refers to `curr` any more, so `curr` is out of the list — it is *unreachable*, which is the only definition of "removed" a linked structure has. Whether the node's storage is then reclaimed automatically or must be released by hand is an environment question, not a list question; the list-level fact is that a single reference write does the removal. ### Why the cost is not O(1) The splice is O(1); finding `prev` is not. If the caller says "remove the job with this identifier" or "remove the node at position k", you must start at the head and walk, because forward links cannot be traversed backwards. That walk is O(n) in the worst case (the target is at the end, or absent). The honest statement of cost is therefore two-part: | You are given | Cost of removal | | --- | --- | | The predecessor node | O(1) | | A value or position | O(n) — the search dominates | | Only the node to remove | O(n) in general; see the payload-copy substitute | Collapsing this into "linked lists have O(1) deletion" is the classic half-truth. The property that is genuinely O(1) is *splicing*, not *deleting an arbitrary element*, and interviewers ask this question precisely to see whether the candidate separates the two. ### The trailing-reference walk The standard search therefore carries two references: `curr`, which inspects nodes, and `prev`, which lags exactly one behind. Both must be maintained together or the splice at the end has nothing to write into. This is also where the most common beginner bug lives. ### The bug: moving a variable instead of rewriting a link Writing `curr = curr.next` *feels* like removal — after it, the local variable no longer names the node. But `curr` is a local traversal cursor, not part of the list. The predecessor's link is untouched, so a walk from the head still visits the node, the length is unchanged, and the node is still holding its payload alive. Nothing in the data structure was written. The rule to internalise: **removal is a write into a node, never a reassignment of a local variable.** Similarly, `curr.next = nil` does not remove `curr`; it truncates the list *after* `curr`, discarding everything downstream while leaving `curr` firmly linked in — usually a much worse bug, because it silently loses data. ### The first node When the target is the first node there is no predecessor to rewrite. The reference that keeps it in the list is the list's own head reference, held by the container or by the caller, so *that* is what must be reassigned: `head = curr.next`. Any removal routine written in terms of `prev.next` alone will silently fail on this case, and a test suite that only removes interior nodes will not catch it. Expect the interviewer to hand you a one-node or two-node list to see whether you branched. ### The contrast that makes the point In a doubly linked list each node also stores a backward reference, so a node you hold gives you both neighbours and removal is genuinely O(1) anywhere in the list — including the last node. You buy that with one extra reference per node (real memory across a large list) and with a second link to keep consistent on every splice, which is a second opportunity to corrupt the structure. The comparison is worth stating out loud in an interview because it shows you understand that O(1) arbitrary removal is not a property of "linked lists"; it is a property you pay for with back-links. ### What to say in the room Name the invariant — a node is in the list exactly when something reachable from the head points at it — then derive everything from it: the splice is one write into the predecessor, the search for the predecessor is the O(n) part, the head has no predecessor and needs the head reference reassigned, and moving a cursor changes nothing at all.
- So is removal from a singly linked list O(1) or O(n)?Both, depending on what you are handed. Given the predecessor, the splice is a single reference write, O(1). Given a value or a position, you must walk from the head to find that predecessor, which is O(n) — and the walk, not the write, dominates. Quote the two-part answer rather than the slogan; "linked lists delete in O(1)" is the answer interviewers are probing for.
- What changes when the node to remove is the first one?There is no predecessor whose link you can rewrite, so the reference that must change is the list's own head reference: `head = curr.next`. A routine expressed purely as `prev.next = curr.next` silently no-ops on that case. It is the boundary interviewers hand you as a one-node or two-node list, and it is why removal routines carry an explicit branch for an empty predecessor.
- Why does a doubly linked list not need the search?Each node stores a backward reference as well as a forward one, so a node you already hold hands you both neighbours and the splice becomes two writes with no walk — O(1) anywhere, last node included. The price is one extra reference of memory per node and a second link to keep consistent on every insert and remove, which is a second chance to corrupt the chain.
Each node is a signpost that only points forward. To stop traffic reaching a signpost you change the sign before it — repainting the signpost itself, or walking past it, changes nothing about where drivers end up.
saying these in an interview costs you the question
- Claiming linked lists always delete in O(1)
- Believing curr = curr.next unlinks the node
- Setting the node's own next to nil to remove it
- Forgetting the first node has no predecessor
- Thinking the node can detach itself from the list