P-4.2 Linked Lists

What this is and why it exists

Linked storage trades away indexing to buy cheap insertion and deletion at a position you already hold.

The classical analysis says this makes it better than an array for insert-heavy work. On modern hardware it frequently does not, because nodes scattered around memory defeat the processor's cache.

Both of those are true. Being able to hold them together is more useful than knowing either alone. It is also an early lesson in the limits of counting operations.

The vocabulary

• Node — one element, holding a value and the address of the next.
• Head — the first node, and the only one you get for free.
• Traversal — walking from the head to reach a position.
• Splice — inserting or removing a node by reassigning links.
• Doubly linked — each node also holds the address of the previous one.
• Cache — fast memory the processor fills in blocks, not single bytes.

The mental model

A node holds a value and the address of the next node. The structure is a chain rather than a block. That means it grows one node at a time and never copies what is already there. An array cannot offer that, because an array's growth is a copy.

Insertion and deletion are constant time once you are there. Splicing a node in or out is a couple of assignments, and nothing shifts. Those four words carry all the weight, though, because getting there is a walk from the front.

And there is no indexing. Without contiguous storage there is no arithmetic that jumps to a position, so reaching the tenth element means visiting nine others. Any algorithm that indexes repeatedly is the wrong fit, and no clever implementation will rescue it.

A doubly linked list stores the previous node as well. That buys two things: you can walk backwards, and you can delete a node given only that node, without having tracked what came before it. The cost is another address in every node and two more assignments in every update.

Now the modern caveat, which the classical analysis does not include. Processors fetch memory in blocks, not bytes. Walking contiguous storage means the next several elements arrive with the one you asked for. Following addresses scattered around the heap means a separate trip for each. The difference is often large enough to reverse the ranking that operation-counting predicted.

So the honest position has three parts. Linked lists win on the operation count for insert-heavy work. Arrays frequently win on the clock, and when the two disagree, measurement wins.

What you should now be able to explain or do

Implement a singly and a doubly linked list. State which operations are genuinely cheaper than in an array, and be precise about the condition attached. Explain why there is no indexing and what that rules out. Say what the second link buys and what it costs. Explain why an array is often faster in practice despite the analysis, and say which evidence you would trust.

Check yourself