In a linked list, why is there no address arithmetic to reach the k-th node?
answer
- What must be true to compute an address
- Same size, one after another
- Nodes are separate allocations
- Only the link field says where next is
- No base plus stride means walking
basics
~20 sA linked list's nodes are separately allocated and scattered in memory, so there is no base address plus fixed stride to compute. Each node knows only where the next one lives, so reaching index k means following k links.
solid answer
~50 sConstant-time indexing needs two guarantees: elements of a known fixed size, laid out contiguously from a known base address. A chain of nodes gives you neither. Each node is its own allocation, handed out wherever the allocator had room, and the only thing holding the structure together is that every node stores a reference to the next one. There is no `base + k * stride` to evaluate — the address of node k is genuinely unknown until you have read the k-1 nodes before it, so positional access is O(k) and O(n) in the worst case. Worse, those are *dependent* loads: hop k cannot start until hop k-1 has returned its address. The compensation is that nodes never move, so a reference you hold into the middle of the chain stays valid for the life of that node.
code
pseudocode · 13 lines// each node is its own heap record:
// node.value - the payload
// node.next - reference to the next record, or null at the end
node_at(head, k):
node = head
for i in 0..k-1:
if node == null:
return null // ran off the end
node = node.next // address known only after this load returns
return node
// cost: k hops, each one dependent on the previousgo deeper
Be ready to say what a node contains — a value and a reference to the next node — and why that forces a walk from the head to reach position k. Naming the two guarantees that constant-time indexing needs is the whole answer.
Explain the mechanics: separate allocations mean no base address and no uniform stride, so the address of node k exists only after the previous k reads. Mention that the hops are dependent loads, not just more instructions.
Show you have seen the cost in production: an O(n) pass over a chain and an O(n) pass over a contiguous block are not interchangeable, and a loop that re-resolves positions from the head is the quadratic bug that shows up under real data volume.
Own the trade being made. Giving up positional arithmetic and locality buys stable addresses and size-independent local edits; be able to say which of those a given workload actually needs before a team commits to the layout.
## Two ingredients make indexing constant time When a container answers "give me element k" in constant time, it is doing arithmetic, not searching. That arithmetic needs exactly two guarantees: 1. **Uniform stride** — every element occupies the same number of bytes, so position k is k strides from the start. 2. **Contiguity** — the elements sit in one unbroken block starting at a known base address. Given both, the address of element k is `base + k * stride`: a multiply, an add, and one load. Notice what is missing from that expression — `n`. The size of the container never enters it, which is exactly why the cost does not grow with the container. ## What a node actually is A linked-list node is a small independent record on the heap. It holds the payload (the value, or a reference to it) and a link field: a reference to the next node, or a null terminator at the end. The owner of the list holds one reference — the head. Every other node is reachable *only* by starting there and following links. The crucial point is where those records live. Each one is a separate allocation request, satisfied wherever the allocator happened to have a suitable free block at that moment. Two nodes created back to back may land beside each other; two nodes created ten minutes apart, with other allocations in between, may land megabytes apart. Nothing in the structure enforces or even prefers an ordering in memory. **The order of a linked list is logical, not physical.** The chain is a story the link fields tell about records whose actual addresses are arbitrary. So neither ingredient holds. Stride is meaningless because nodes are not spaced regularly, and there is no base address for the sequence because the sequence has no block of its own. The arithmetic has nothing to work with. ## Consequence one: positional access is traversal To reach index k you start at the head and follow the link field k times. That is O(k) hops, O(n) for the last element, and O(n) if you scan from the head repeatedly — the classic quadratic accident is a loop that walks positions 0, 1, 2, ... by re-traversing from the head each time, turning an O(n) pass into O(n^2). A traversal must also respect the terminator invariant: after each hop, the reference may be null, and reading a field off it is the standard crash in beginner code. That is why the hop and the null check belong in the same loop body. ## Consequence two: the hops are dependent There is a second, subtler cost that big-O hides. Scanning a contiguous block, the machine knows every address it will need in advance; the reads can be issued and overlapped. Walking a chain, the address of the next node is *inside the node you are currently reading*. The load for hop k cannot even be issued until the load for hop k-1 has come back. If the nodes are scattered, each hop is a memory access whose latency cannot be hidden behind the previous one, so the delays add up rather than overlap. Two structures can share the label O(n) for a full pass and still differ by an order of magnitude in wall-clock time for exactly this reason. Big-O counts operations; it does not price them. ## Consequence three: what the layout buys you The same property that kills indexing is what the structure is for. Because a node is its own allocation, it never moves: adding a million more elements does not relocate the node you are looking at, and a reference you stored to it days ago still points at it. There is no capacity, no growth threshold, and no bulk copy — the structure grows by one allocation at a time. And because neighbours are joined only by link fields, changing the sequence around a node you already hold is a couple of reference writes, not a shift of everything after it. That is the actual trade the node-and-pointer model makes: it gives up positional arithmetic and memory locality, and gets back stable addresses and local, size-independent restructuring. ## Where candidates go wrong The common failure is answering as if a linked list were an array with extra steps — "the runtime knows where node k is", or "it caches positions after the first pass". There is no hidden index; the only map from position to address is the walk itself. The other failure is dismissing O(n) indexing as "a bit slower": at ten million elements, a positional loop written the naive way is not a bit slower, it is a different program.
- If positional access is O(k), why does anyone iterate a linked list at all?Iterating from the head to the tail once is O(n) total, because you keep the current node reference and hop from it. The quadratic trap is asking for position 0, then 1, then 2 from the head each time — that re-walks the prefix and turns an O(n) pass into O(n^2). Iterate with a cursor you carry, never with a position you re-resolve.
- Why does a full traversal of a chain often run far slower than a contiguous scan of the same element count?Both are O(n) passes, but the per-element cost differs. A contiguous scan knows all its addresses up front, so memory reads overlap. In a chain, the address of the next node lives inside the current node, so each read must complete before the next can be issued. Scattered nodes turn that into a serialized chain of memory latencies that big-O never mentions.
- What does the node-and-pointer layout give you that contiguous storage cannot?Address stability. A node never moves as the structure grows, so a reference you took to it stays valid indefinitely, and inserting or removing near it touches only the neighbouring link fields instead of shifting or reallocating everything else. That is what makes a held-node edit cheap regardless of how large the structure is.
Numbered lockers let you walk straight to locker 400 because they are the same size and in a row. A treasure hunt gives you one clue at a time, and the only way to reach the fourth clue is to find the first three.
saying these in an interview costs you the question
- Says the runtime keeps a hidden index of node positions
- Assumes nodes are laid out consecutively in memory
- Claims positions get cached after the first traversal
- Calls indexing O(1) because 'following a pointer is fast'
- Re-walks from the head inside a loop and calls it linear