Linked lists

A treasure hunt where each clue says where the next one is

A linked list stores items wherever there is free memory, and each item carries the address of the next one. Each item is called a node: a value plus a pointer, which is just the memory address of the next node.

Take the list 3 → 8 → 5. A pointer called the head leads to the node holding 3; 3 points to 8, 8 to 5, and 5 to null, a 'nothing' value marking the end. Like a treasure hunt, you reach 5 only by following clues from the start.

Unlike an array's items, nodes aren't side by side, so item k's address can't be computed: reaching it takes k − 1 hops, which is O(n). A doubly linked list adds a pointer back to the previous node, so you can walk both ways.

Linked lists

How the Linux kernel keeps track of every running program

The Linux kernel describes each running program with a record called task_struct and chains these records using its built-in doubly linked list type, list_head. Programs start and exit constantly, and no other record has to move.

Outside the kernel, Java's LinkedList class is a doubly linked list. Caches that evict the least recently used item, like memcached, keep items in a linked list so a used item moves to the front in O(1).

Linked lists

Adding an item means rewriting two arrows, not moving a million items

To put 7 between 3 and 8, create a node for 7, point it at 8, then point 3 at 7. Nothing else moves. Order matters: if you repoint 3 first, you lose the only path to 8 and everything after it.

Deleting 8 is one change: point 3 straight at 5. In an array, inserting or deleting at the front shifts every later item one slot, which is O(n).

The catch is finding the spot: without a pointer to it, you walk there in O(n). And since nodes are scattered in memory, walking a list is slower than scanning an array, which the CPU reads in consecutive blocks.