Under what condition is inserting into a linked list truly O(1)?
answer
- Ask where the insertion point comes from
- Split the operation into locate and splice
- Splicing itself is only reference writes
- Someone has to reach that node first
- The walk, not the splice, dominates
basics
~20 sOnly when you already hold a reference to the node you are splicing next to. Then it is a fixed number of reference writes. If you must first reach the position by index or by searching, that walk is O(n) and dominates the cost.
solid answer
~50 sThe O(1) claim covers the splice, not the search. Given a node you already hold, inserting after it is two reference writes and no elements move — genuinely constant, and independent of list length. But most real inserts are specified as "at index k" or "before the first element matching X", and neither is reachable by arithmetic in a linked layout: you walk from the head, which is O(k) or O(n). So the honest scorecard reads: insert at head O(1); insert at a **held** node O(1); insert at a **found** position O(n) walk plus O(1) splice. The array's mirror image is the opposite shape: reaching position k is O(1), but making room shifts the tail, which is O(n). Both are linear for a positional middle insert — the difference is what the linear part is made of.
code
pseudocode · 12 lines// insert value v after the k-th node of list L
node = L.head
i = 0
while i < k and node != null
node = node.next // one dependent hop per step
i = i + 1
if node == null
return error
fresh = new_node(v)
fresh.next = node.next // splice: write 1
node.next = fresh // splice: write 2
...go deeper
Know that a linked list rearranges references while an array shifts elements, and that the head is the one position a list can always reach for free. Say plainly that reaching a numbered position in a list requires walking to it.
Split every insert into locate and splice, and give the four-row scorecard: head, held node, found position, and index access. Explain why an O(n) locate wipes out an O(1) splice and cannot be amortised away.
Demonstrate that you look at how callers specify positions before believing an O(1) claim. Point out that a loop of scanned inserts is quadratic regardless of splice cost, and name the singly-versus-doubly asymmetry for deletion.
Frame the choice as who is expected to hold node references. A structure whose fast path requires callers to carry stable handles pushes complexity into every call site; decide whether the team can maintain that discipline or whether the simpler contiguous container is the responsible default.
## Separate the two halves of an insert Every insertion is two operations wearing one name: 1. **locate** — get to the place where the new element goes; 2. **splice** — actually put it in. The famous "linked lists insert in O(1)" is a claim about the *second* half only. Quoting it as if it covered the whole operation is the single most common wrong answer in this comparison, and it is what an interviewer is fishing for. ## The splice really is constant Given a node `p` you already hold in hand, inserting a new node after it is: ``` fresh = new_node(v) fresh.next = p.next p.next = fresh ``` Two reference writes plus an allocation. Nothing else in the list is touched: no element is copied, no later position is disturbed, and every existing reference to any other node stays valid. The cost does not depend on the list's length — this is real O(1), and it is the property the structure exists for. ## Locating is where the cost hides The trouble is that application code rarely arrives holding `p`. It says "insert at position k" or "insert before the first entry with this identifier". In a linked layout neither can be answered by arithmetic, because node addresses have no pattern; the only procedure is to start at the head and hop: - insert at index k: O(k) hops, O(n) worst case; - insert before a searched-for element: O(n) hops. The splice that follows is O(1), but O(n) + O(1) is O(n). And this walk is not amortisable: doing it repeatedly does not make later walks cheaper. Insert n elements at scanned positions and you have an O(n²) loop, no matter how cheap each individual splice was. Two positions escape the walk because the structure keeps a reference to them directly: the **head** (always) and the **tail** (when the list maintains a tail reference). Insertion and removal at those ends are genuinely constant, which is why linked structures make good queues and stacks. ## The array's mirror image Run the same split on a contiguous array: - **locate** position k: O(1), pure arithmetic; - **splice** at k: shift every element from k to the end one slot along, O(n − k), so O(n) in the middle. The two structures have swapped which half is cheap. For a positional middle insert both are linear overall — the asymptotic table shows a tie that beginners often read as a win for the list. The tie-breaker is what the linear work consists of. The array's shift is a bulk move of adjacent memory: a predictable, streaming access pattern that hardware moves in wide chunks. The list's walk is a chain of loads where each address is only known once the previous load returns, so it cannot be run ahead of. Same complexity class, very different measured cost — usually a large multiple in the array's favour for the same n. ## The honest scorecard | operation | contiguous array | linked list | | --- | --- | --- | | access by index | O(1) | O(n) | | insert/remove at head | O(n) (shift) | O(1) | | insert at a **held** node | O(n) (shift) | O(1) | | insert at a **found** position | O(1) locate + O(n) shift | O(n) walk + O(1) splice | | memory per element | the element | element plus one or two references, plus per-node allocation overhead | The rows where the list genuinely wins are the head row and the held-node row. That is a narrow but real win, and being able to name exactly those rows — rather than waving at "lists are better at inserts" — is what a middle-level answer looks like. ## Deletion behaves the same way, with one extra catch Removing a node you hold is O(1) in a doubly linked list, because the node's own backward reference gives you its predecessor. In a singly linked list, holding the node to delete is **not** enough: you need the node *before* it to redirect, so you are back to an O(n) walk unless the caller kept the predecessor. This asymmetry catches candidates who have memorised "delete is O(1)" without asking which links exist. ## Traps - Quoting O(1) for an insert whose position is specified by index or by search. - Forgetting that maintaining a size counter, or a tail reference, is what makes some "O(1)" claims true; without a tail reference, appending walks the whole list. - Assuming the array's O(n) shift and the list's O(n) walk cost the same because the notation matches.
- You hold a reference to the node you want to delete. Is deletion O(1)?In a doubly linked list, yes — the node's backward reference gives you the predecessor, so you rewire two references. In a singly linked list, no: you need the node before it to redirect, and finding that means walking from the head, so it is O(n) unless the caller already kept the predecessor.
- Appending to a linked list is often quoted as O(1). Under what condition?Only if the list maintains a reference to its tail and keeps it correct on every structural change. Without one, appending walks the entire list to find the last node, which is O(n) per append and O(n squared) for n appends — a common cause of a loop that mysteriously degrades on large inputs.
- Both structures are O(n) for a middle insert at a searched position, so is it a wash?No. The linear work differs in kind: the array shifts a contiguous run, a bulk move of adjacent memory that hardware streams efficiently; the list follows a chain of loads where each address is revealed only when the previous one arrives. Same class, and typically a large measured gap favouring the array.
saying these in an interview costs you the question
- Quotes O(1) insert without saying at a held node
- Forgets the walk to reach position k
- Claims delete is O(1) in a singly linked list given only the node
- Assumes appending to a list is O(1) with no tail reference
- Reads the tied O(n) row as a win for the list