Arrays vs Linked Lists

## The question behind the question "Index access" means: given a position `i`, produce element `i`. Interviewers ask this first because the answer exposes whether you think about *layout* — how the data physically sits in memory — or only about the names of operations. ## Why the array is O(1) An array is defined by two properties that must both hold: 1. every element occupies the **same number of bytes**, and 2. the elements are **contiguous** — element `i+1` begins exactly where element `i` ends. Together those give a closed-form address: ``` address(i) = base + i * elementSize ``` One multiply, one add, one load. The expression contains no loop and no dependence on how many elements exist, so the cost is the same for the first element and the millionth. That is what O(1) means here: constant *with respect to n*, not "free". Note what the array does **not** store: there is no per-element bookkeeping, no forward reference, no index table. The position information is implicit in the geometry. This is also why an array cannot grow in place indefinitely — the contiguity that buys O(1) access is exactly what a resize must reconstruct elsewhere. ## Why the linked list is O(n) A linked list is a set of independently allocated nodes. Each node holds a value and a reference to the next node; the list itself holds only a reference to the head. The nodes may be anywhere, in any order, arbitrarily far apart. Nothing in that layout encodes distance. There is no arithmetic that turns `i` into an address, because the addresses have no pattern. The only available procedure is: ``` node = head for step in 0..i-1 node = node.next return node.value ``` That is `i` hops, so O(i), and O(n) in the worst case. A doubly linked list, which stores a backward reference too, lets you start from the nearer end and so halves the worst case — but halving a linear cost leaves it linear. It is a constant-factor improvement, not a complexity change. ## Why the gap is wider than the notation suggests The asymptotic answer (O(1) versus O(n)) is only half of what a strong candidate says. The other half is that each link hop is a **dependent** load: the machine cannot begin fetching node `k+1` until node `k` has actually arrived, because node `k` contains the address. Hardware is very good at hiding memory latency when it can predict what is needed next — a sequential scan over a contiguous block is the easiest prediction there is — and very bad at hiding it when each address is only revealed at the last moment. So the walk pays close to full memory latency per hop, while the array's arithmetic pays essentially nothing. The consequence is the one that surprises people: even for operations where the two structures share the same complexity class — a full front-to-back scan is O(n) for both — the contiguous structure routinely measures several times to an order of magnitude faster on the same data. Big-O is an upper bound on growth; it deliberately says nothing about constants, and here the constants are the whole story. ## What the list gets in return Be fair to the list, or the answer sounds rehearsed: - it needs no single contiguous block, so it can grow when memory is fragmented; - inserting or removing next to a node you **already hold** is a fixed number of reference writes, with no elements moved; - references to existing nodes stay valid as the list changes around them. None of those requires positional access, which is the point: the list is a structure for *positions you are already standing at*, not for positions you have to name by number. ## Traps - "A doubly linked list gives random access." It does not; it gives a second direction to walk. - "Index access on a list is O(n), but n is small so it is fine." Sometimes true — but say it as a measured claim about your sizes, not as a reflex. - "Arrays are O(1) for everything." Only for access by index. Inserting or deleting in the middle of an array shifts the tail, which is O(n). A useful one-line summary: an array knows *where* everything is; a linked list only knows *what comes next*.