Linked structures

Inserting into the middle of an array is linear because the elements are neighbours in memory, and the only way out is to stop requiring that they are.

A node that names its successor

The alternative to one block is many small blocks, each holding one element together with the address of the next. Such a block is a node, the address it holds is a pointer or reference, and a chain of them is a singly linked list. The list itself is nothing but a pointer to the first node, called the head; the last node's pointer is null, which is how the end is recognised.

The nodes may sit anywhere in memory, in any order. Nothing about their addresses encodes their position in the sequence, and that single fact generates the entire cost table.

Consider inserting a new value between two existing nodes. You allocate a node, point it at the second node, and rewrite the first node's pointer to point at the new one. Two pointer writes, one allocation, done, regardless of how long the list is or where in it you are. The array had to move $n - k$ elements to achieve the same thing; the list moves nothing, because nothing is where it is for a reason.

Deletion of the node after a known node is the same idea: copy the doomed node's pointer into its predecessor and release it. Again constant, again independent of length.

That is the purchase. Now the price.

What contiguity was paying for

To reach the element at position $i$ , there is no arithmetic to do, because the address of node $i$ is not a function of $i$ . It is stored inside node $i - 1$ , whose address is stored inside node $i - 2$ , and so on. The only way to find it is to start at the head and follow $i$ pointers. Indexing is $Θ (n)$ where the array's was $Θ (1)$ .

This poisons more than it first appears to. The constant-time insertion above assumed you already held a pointer to the node you were inserting after. If you know only the position, you must walk to it first, and the walk is linear, so "insert at position $k$ " costs $Θ (k)$ in a linked list and $Θ (n - k)$ in an array. Neither is better in general; they are expensive in opposite places.

The honest statement is therefore narrow: a linked list gives constant-time insertion and deletion at a position you already hold a reference to. That is exactly the situation in an LRU cache, where a hash table hands you the node directly, or in an iterator that is already standing where it needs to edit. It is not the situation in most code, which is why the array wins more often than the textbook cost table suggests.

Example. A structure holds 10,000 elements and you want to insert a value at position 5000, knowing only the position. Count the elementary operations for an array and for a singly linked list.

The array shifts every element from index 5000 to 9999 one slot right: $10000 - 5000 = 5000$ moves, then one write. The list follows 4999 pointers to reach node 4999, then does two pointer writes: about 5001 operations. The counts are within a fraction of a per cent of each other, both $Θ (n)$ , and the array's operations are sequential memory writes while the list's are scattered reads, so the array is faster in practice by a wide margin.

Now you. The same two structures, but now you want to insert at position 100. Count the operations for each.

Answer

The array shifts $10000 - 100 = 9900$ elements. The list follows 99 pointers and writes two: 101 operations. Near the front the list wins by a factor of about 98, and near the back the array wins by the same kind of margin. The position of the edit, not the structure alone, decides.

Doubly linked, and what the second pointer buys

A singly linked list cannot delete a node it is standing on, because deletion requires rewriting the predecessor's pointer and the predecessor is unreachable. It also cannot be walked backwards. Both are fixed by giving each node a second pointer, to its predecessor, producing a doubly linked list.

Now deleting a node you hold is genuinely constant: read its two neighbours from its own fields, point them at each other, release it. Insertion before a known node becomes possible too. Most library list types, including std::list and Java's LinkedList, are doubly linked for these reasons, usually with a sentinel node joining the two ends into a ring so that the empty case and the end cases need no special code.

The cost is memory and bookkeeping. Suppose the payload is an 8-byte number on a 64-bit machine. An array of a million such values occupies 8 MB, exactly the data. A singly linked list needs 8 bytes of payload plus an 8-byte pointer per node, so 16 MB, double. A doubly linked list needs 24 MB, triple. And that is before the allocator: a general-purpose malloc typically adds a header of about 16 bytes to each separate allocation and rounds sizes up, so a real singly linked list of a million small nodes can occupy 32 MB or more, four times the data it holds.

The performance consequence is larger than the memory one. A cache line is typically 64 bytes, so an array of 8-byte elements delivers eight elements per trip to memory: a full scan of a million elements causes about 125,000 memory fetches. The nodes of a linked list, allocated at different times, are scattered, so each hop is likely to be its own fetch: about a million of them. At roughly 100 nanoseconds for a fetch that misses cache, the scan costs about 12 milliseconds against 100 milliseconds, a factor of eight that the step count says nothing about, both being $Θ (n)$ .

Stacks: last in, first out

The interesting move now is not to add capability but to remove it. A stack supports exactly three operations: push a value on the top, pop the top value off, and look at the top without removing it. All three are constant time, and the discipline that results is last in, first out.

Both layouts implement it well. On a dynamic array, push and pop act at the end, which is the cheap end, giving amortised constant cost with excellent cache behaviour. On a linked list, push and pop act at the head, which is the node you already hold, giving true worst-case constant cost with no reallocation ever.

The reason a restricted interface is worth having is that many problems are exactly stack-shaped, and saying so is a design decision rather than an implementation detail. Matching brackets in an expression is: push each opener, and on each closer check that the popped opener matches. Undo histories are. Depth-first search, in the graph lessons, is. And the call stack that made recursion possible in the previous course is literally one: each call pushes a frame holding the parameters and the return address, each return pops one, and a runaway recursion overflows it, which is what a stack overflow is.

Queues, and the ring buffer

A queue reverses the discipline: enqueue at the back, dequeue from the front, first in first out. It is the right structure whenever fairness or arrival order matters, which is most of scheduling, most of message passing, and the traversal in the graph lessons that finds shortest paths by edge count.

Implementing it on a linked list is immediate: keep pointers to both head and tail, enqueue at the tail, dequeue from the head, both constant.

Implementing it on an array takes one idea. Dequeuing from index 0 and shifting everything left is $Θ (n)$ and unacceptable, so instead the queue keeps two indices, a head and a size, and lets the contents wrap around the end of the block. Element $i$ of the queue lives at slot $(head + i) mod capacity$ . Enqueue writes at $(head + size) mod capacity$ and increments the size; dequeue returns slot head, advances head modulo the capacity, and decrements the size. That is a ring buffer or circular buffer, both operations constant, no shifting, no allocation, and it is what sits behind most audio pipelines, network buffers and lock-free producer-consumer channels.

A deque, or double-ended queue, allows insertion and removal at both ends, and is what you get by allowing head to move backwards too. Python's collections.deque is a linked list of fixed-size blocks; C++'s std::deque is an array of pointers to fixed-size blocks. Both are attempts to get the ring buffer's locality without its fixed capacity.

Example. A ring buffer has capacity 8, its head is at slot 6, and it currently holds 5 elements. Which slot holds queue element 3, and which slot will the next enqueue write to?

Element $i$ is at $(6 + i) mod 8$ , so element 3 is at $(6 + 3) mod 8 = 1$ . The next enqueue writes at $(6 + 5) mod 8 = 3$ . The occupied slots are 6, 7, 0, 1, 2, which is the wrap that gives the structure its name.

Now you. From that state, two elements are dequeued and three are enqueued. Where is the head now, how many elements are held, and which slot holds element 0?

Answer

Two dequeues move head from 6 to $(6 + 2) mod 8 = 0$ and the size drops to 3. Three enqueues raise the size to 6, writing at slots $(0 + 3) mod 8 = 3$ , then 4, then 5. Element 0 is at the head, slot 0. The buffer now holds 6 of its 8 slots, occupying 0 through 5.

Choosing between them

The cost table is the smaller half of the decision, and it is worth writing out honestly, with $n$ the number of elements.

operation	dynamic array	singly linked	doubly linked
access element $i$	$Θ (1)$	$Θ (i)$	$Θ (i)$
insert or delete at front	$Θ (n)$	$Θ (1)$	$Θ (1)$
insert or delete at back	$Θ (1)$ amortised	$Θ (1)$ with a tail pointer	$Θ (1)$
insert after a held node	$Θ (n)$	$Θ (1)$	$Θ (1)$
delete a held node	$Θ (n)$	$Θ (n)$	$Θ (1)$
memory per 8-byte element	8 to 16 bytes	32 bytes typical	40 bytes typical
full scan of $10^{6}$ elements	about 12 ms	about 100 ms	about 100 ms

The last two rows are why the recommendation from practice is blunter than the table above them: prefer the dynamic array unless you have a specific reason not to. The reasons that count are holding stable references to elements that must survive insertions elsewhere, splicing whole sublists in constant time, needing a hard worst-case bound with no reallocation pause, and hardware without enough contiguous memory to hold a large block.

Example. A program keeps a list of a million records and its dominant operation is walking the whole list to sum a field, done thousands of times. Occasionally a record is inserted in the middle. Which structure?

The dynamic array. The dominant operation is a scan, where the array wins by about a factor of eight on memory traffic; the rare insertion costs $Θ (n)$ , about half a million moves of contiguous memory, which is a few hundred microseconds and happens rarely. Optimising the rare operation at the cost of the frequent one is the standard way to make a program slower while believing you improved it.

Now you. A cache holds a million entries and must, on every access, move the accessed entry to the front of a recency order, given a pointer to it from a hash table. Which structure, and why?

Answer

A doubly linked list. The operation is "unlink a node I already hold and relink it at the front", which is constant time only when the node knows both neighbours. In an array the same move is $Θ (n)$ per access, and with a million entries accessed constantly that is fatal. This is the design of every LRU cache, and it is the case where the list genuinely wins.

Both layouts share one weakness, and it is total. To find an element whose position you do not know, there is nothing to do but look at them all: $Θ (n)$ , for an array and for a list alike, no matter how the memory is arranged. The next lesson removes that cost, at the price of a precondition that nothing so far can supply.