Linked lists

A linked list stores each item in its own small record, a node, which holds two things: the value, and a reference to the next node (its next). The first node is the head. The last node's next is nothing, which is how you know the list has ended.

Unlike an array's items, nodes don't have to sit together in memory. Each one can be wherever there was room when it was created, because the order is stored in the arrows, not in the addresses.

In the pseudocode on these pages, Node(x) makes a new node holding x whose next is nothing, and node.value and node.next read or change its two fields.

An array finds item i with one calculation, because item i is at a known offset from the start. A linked list has no such shortcut: the only way to the fourth node is through the first three. Reading the item at position i takes i steps, and finding a value takes up to n: both O(n).

That walk is the price of everything that follows. It is also why linked-list code is full of loops like this one, which stops at the node holding a value:

Inserting after a node moves no other item. You make the new node, point it at the node that came next, and point the current node at it:

The order of those two lines matters. If you pointed the current node at the new one first, the only reference to the rest of the list would be overwritten, and the rest of the list would be lost.

Deleting is one arrow: point the node before the one to remove past it. Nothing refers to the removed node any more, so the language reclaims it (or, in C and C++, you free it yourself). Because you need the node before, the walk stops one node early:

Note the special case at the top of the delete: if the value is in the head, there is no node before it, and the list simply starts one node later. That kind of edge case is where linked-list bugs live.

Reversing a linked list is a favorite interview question because it is all about not losing the rest of the list. Walk the list once with three references: prev (the part already reversed), node (the one being turned around) and ahead (where the rest of the list starts, saved before the arrow changes). The walkthrough reverses only a stretch in the middle, so it also has to stitch both ends back in: the node before the stretch, and the rest after it.

Every node is visited once and nothing is copied: O(n) time and O(1) extra space. The nodes never move; only their arrows do.

A plain list knows only its head, so adding at the end means walking the whole list. Keeping a second reference to the last node, the tail, makes appending O(1).

A doubly linked list gives every node a prev as well as a next. You can then walk backward, and delete a node given only the node itself, because it knows its neighbor on each side. The cost is one more reference per node, and two more arrows to keep right on every change.

Many implementations also start the list with a sentinel: a dummy node that holds no value and is always there. Every real node then has a node before it, so the head special case in the delete above disappears.

The table makes linked lists look good, but two costs don't show in Big-O. Each node carries at least one extra reference, and in languages like Java or Python each node is a separate object with bookkeeping of its own. And because nodes are scattered in memory, walking a list jumps around instead of reading memory in order, which modern processors handle much worse than an array scan.

So arrays are the default. Linked lists earn their place when items are added and removed in the middle of a long sequence all the time, through references you already hold, and as a building block inside other structures.