Linked lists: giving up indexing to buy insertion

An array insists its values sit next to each other. A linked list gives that up, and gets something in return.

The idea#

Each value lives in its own little box, called a node. A node holds two things: the value, and the address of the next node.

[ 3 | -]--> [ 7 | -]--> [ 1 | -]--> null

The boxes can be anywhere in memory, in any order. What holds the list together is that each one knows where the next one is. The last node points at null, which is how you know you have reached the end.

You keep one reference to the first node, usually called the head. Lose that and the whole list is unreachable.

What this costs you#

There is no arithmetic that finds node 7. The addresses are unrelated, so the only way to reach the seventh node is to start at the head and follow the links seven times.

That table is the whole lesson. A linked list is an array with the costs turned inside out.

Why inserting is instant#

To put a new node between 3 and 7, nothing shuffles. You change two links:

before:  [ 3 | -]--------> [ 7 | -]--> ...

after:   [ 3 | -]--> [ 5 | -]--> [ 7 | -]--> ...

1. Point the new node at 7.
2. Point 3 at the new node.

Two assignments, regardless of whether the list holds ten values or ten million.

The order matters. Point 3 at the new node first, and you have lost your only reference to 7 and everything after it. This is the single commonest linked list bug, and it is worth drawing on paper every time until it is automatic.

Two links instead of one#

A doubly linked list gives each node the address of the previous node as well.

null <--[- | 3 | -]<-->[- | 7 | -]<-->[- | 1 | -]--> null

That buys you walking backwards, and removing a node you hold without needing its predecessor. It costs one more address per node, and every operation now has two links to keep straight instead of one.

When to actually use one#

Honestly: less often than interview questions suggest. Arrays win most of the time, because jumping around memory is slower in practice than the cost table admits, for reasons about how processors fetch memory in blocks.

Linked lists earn their place when:

• You insert and remove constantly and rarely look things up by position. A queue, or the list behind an LRU cache.
• You are already holding the node you want to remove.
• You must never copy the values, because they are large or something else points at them.

Where you have already used one#

The chain of items sharing a hash bucket. An undo history. A queue in a scheduler. The scope chain in a language runtime. Once you see the shape, it turns up constantly.

Common mistakes#

• Rewiring links in the wrong order and dropping the rest of the list.
• Forgetting to update the head when you insert or remove at the front.
• Walking off the end because you checked node.next instead of node.
• Reaching for a linked list to "avoid resizing" when a growable array is faster in practice.