Why does removing a node from a singly linked list need the predecessor, and what does that cost?

### 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.