Why is splicing a node into a chain O(1) only when you already hold the node?
answer
- Count the writes, then count the walk
- Which link fields actually change
- Nothing after the point shifts
- How did you get that reference
- Locate cost plus rewire cost
basics
~20 sRewiring is a fixed number of reference writes that touch only the nodes next to the splice point, so it costs the same at ten elements or ten million. Finding that splice point is a separate O(n) walk, and the O(1) claim covers only the rewiring.
solid answer
~50 sThe splice itself writes a constant number of link fields: the new node's link points at the current successor, the held node's link points at the new node, and nothing else in the structure is touched — no elements shift, no block is reallocated, and every other node keeps its address. That cost is independent of the number of elements, which is where O(1) comes from. But it is conditional: you must already be holding the node the write goes through. If all you have is "insert at position k" or "insert after the element equal to x", you first pay an O(k) or O(n) traversal to find it, and the traversal dominates. So the accurate claim is "O(1) *given a reference to the splice point*". A text editor gets the good case for free because the cursor already is that reference; a caller that only knows a position does not.
code
pseudocode · 11 lines// cursor is a reference the caller already holds into the chain
// new_node.value is already set
splice_after(cursor, new_node):
new_node.next = cursor.next // 1: new node publishes the rest of the chain
cursor.next = new_node // 2: only now is it reachable
// nothing else in the chain is read or written
// every other node keeps its address
// cost: 2 writes, independent of the number of elements
// cost of OBTAINING cursor: not counted here - that is the other halfgo deeper
Be able to describe the splice as two link writes and say that no other elements move. Knowing that the structure is not shifted or copied is the core of the answer at this level.
Explain the cost as locate plus rewire, and state which callers get the good half. Also be ready to say why the write order matters and which node's link field is actually changed.
Show how the condition drives an API: expose cursors rather than positions so callers can hold their edit points, and recognize an insert-by-position call site as an O(n) per edit pattern hiding behind a constant-time claim.
Own the design consequence — a structure whose advantage is conditional is only worth its memory cost if the workload actually satisfies the condition. Be able to say when a team's access pattern will never hold edit points, making the choice a mistake.
## The claim and its missing clause "Insertion into a linked list is O(1)" is the single most repeated half-truth about the structure. The full sentence is: *rewiring at a node you already hold* is O(1). Drop the clause and the claim is false for almost every call a real program makes. ## What the rewiring actually costs Given a reference to a node in the chain and a new node to place after it, the work is: 1. Point the new node's link at the held node's current successor. 2. Point the held node's link at the new node. Two writes. Not two writes per element — two writes, full stop. Nothing else in the structure is examined or modified: no elements are shifted along, no larger block is allocated and copied into, and no other node's address changes. That last point matters more than it looks: any reference anyone else is holding into the middle of this chain remains valid across the splice, which contiguous storage cannot promise when it grows. The order of the two writes is not free choice. Publish the new node's link first, then redirect the held node's. Do it the other way and, between the two writes, the tail of the chain is unreachable — a window that is merely sloppy in single-threaded code and a genuine hazard as soon as anything else can observe the structure. ## Where the cost really goes A caller almost never says "splice after *this* node". It says one of: - **Insert at position k.** Resolving k to a node is k hops: O(k), O(n) at the end. - **Insert after the element matching some predicate.** A search: O(n), and there is no way to do better in a bare chain because it supports no ordering-based narrowing. - **Insert after the node I am standing on.** Only this one is O(1) end to end — and it is the case an iteration or a cursor naturally produces. So the honest cost model is `locate + rewire`, and for a chain that is `O(n) + O(1)`. The structure's advantage is not that insertion is free; it is that the *rewire* half does not grow with the collection, so a workload that already holds its edit points pays a size-independent price per edit. ## The scenario that makes it concrete Consider an editor representing a document as a chain of spans, each record naming an offset, a length, and the next span. The cursor is not a character index — it is a reference to a span record. When a paste arrives, the editor allocates a span for the pasted text and splices it in at the cursor: two writes, whether the document is a page or a novel. Nothing after the insertion point moves, so a hundred other references into the document — bookmarks, selections, comment anchors — all stay valid. Contrast the same paste against one flat character buffer, where every byte after the insertion point shifts and every stored offset past it becomes wrong. Notice what made the good case available: the editor *kept* the reference. The moment a feature needs "insert at character offset 40,000" with no cursor in hand, the chain is back to walking spans and summing lengths, and the O(1) splice buys nothing for that call. ## The write must go through the neighbour One more precision that separates a middling answer from a good one. A splice is a write into a link field, so you must hold the node whose link field changes — not merely the node you are conceptually inserting next to. When a chain only carries forward links, inserting *before* a node, or unlinking a node you were handed, needs the node in front of it, and having a reference to the target alone does not give you that. Callers that plan for O(1) edits therefore hold whichever neighbour the write must pass through, or the structure carries enough link fields to reach it. Holding "a node" is not automatically holding the *right* node. ## How to state it in an interview Say the cost as a pair. "The rewiring is constant — two link writes, no shifting, no reallocation, and all other node addresses stay stable. Reaching the splice point is O(k) if I only have a position and O(n) if I have to search. Whether the operation is O(1) depends entirely on whether the caller already holds the node." That answer cannot be attacked, because it prices both halves and names the condition.
- A caller says your O(1) insert is slow. What is the first thing you check?How they reach the insertion point. If they call an insert-at-position or search-then-insert entry point, they are paying an O(n) traversal per edit and the constant-time rewiring is a rounding error. The fix is to hand them a cursor they can hold across edits, so the locate cost is paid once for a batch instead of once per element.
- Why is holding a reference to a node not always enough to unlink it in constant time?Because the write goes into the *previous* node's link field, not the target's. If the chain only carries forward links and the caller kept only the target, finding its predecessor means walking from the head — O(n). Constant-time removal requires holding whichever neighbour owns the link being rewritten, or a layout that reaches it directly.
- Why must the new node's link be set before the held node's link is redirected?Because between the two writes the structure is observable. Setting the held node's link first would briefly point at a node whose own link is not yet set, leaving everything after the splice point unreachable through that window. Publishing the new node fully before linking it in keeps the chain valid after every individual write.
saying these in an interview costs you the question
- States insertion is O(1) without naming the locate cost
- Says nothing shifts, so any insert is constant
- Assumes a position index is as good as a node reference
- Thinks holding the target suffices to unlink it
- Redirects the held node's link before the new node's