Linked lists: cheap to splice, slow to reach

Your music app has a queue of 10,000 songs, and you tap Play next on one more. It has to go straight after the song that is playing. If the queue were an array, every song after that spot would shift one cell along: nearly 10,000 moves for a single tap.

A linked list needs two pointer changes instead. Each song sits in its own node, and each node records where the next one is, so slotting a song in means changing who points at whom. Nothing moves. The price is what an array gave you for free: to reach song 5,000, you start at the first and follow 4,999 pointers, one at a time.

Like a stack or a queue, a linked list is cheap at its ends, with one catch you will meet below. Unlike them, it is also cheap in the middle, as long as you are already standing there.

node

One element of the list: a value and a pointer to the next node. Each node is its own small allocation, wherever memory had room.

next pointer and null

A node’s next says where the following node is. The last node’s next is null (None in Python): nothing comes after it.

head and tail

Pointers to the first and the last node. Everything is reached from head; tail is an extra that makes adding at the back cheap. Both are null in an empty list.

walk (traversal)

Visiting the nodes in order by following next pointers from head, one hop at a time. It is the only way to reach a node in the middle.

singly and doubly linked

In a singly linked list each node points only forwards. In a doubly linked list each node also has a prev pointer back to the node before it.

This list holds 7, 23, 42 and 15. Each box is a node, with its value on the left and its next pointer on the right, where the arrow to the following node leaves. head points at 7, tail at 15, and 15's next is null, drawn as ∅. Insert a value in the middle, then search for one, and watch the two counts.

Nothing was shifted or copied. 42 and 15 kept their places in memory (the drawing only slides them along at the end, to make room for 99 in the row), and two arrows changed: the new node took over 23's link to 42, then 23 was pointed at the new node. That order matters. If 23 pointed at 99 first, nothing would point at 42 any more, and 42 and 15 would be lost. Linking a node in costs those two writes whether the list has 4 nodes or 4 million.

Getting to the spot is another matter. An array finds index i with one calculation, because its cells sit side by side. A list's nodes are allocated one at a time, wherever memory had room, so there is no formula for where node i is: the only way in is head, and the only way along is next. The insert had to walk to 23 before it could link anything, and the search had to look at every node until it reached 15.

The ends are where a list is cheapest. head leads straight to the first node, so inserting or deleting there needs no walk at all. A tail pointer leads straight to the last node, so inserting after it is O(1) too. Deleting the last node is the exception: it changes the node before the tail, and in this list nothing points backwards.

Before each step, predict what comes next: which pointer changes first, whether the node the walk has reached is the one it wants, and how many nodes a walk must pass. Insert 99 at index 2, insert a value at the tail, then delete the value 15.

Reversing a list in place is the classic linked-list exercise, and it shows the one rule of rewiring in its plainest form: save a link before you overwrite it. The loop keeps three names. prev is the part already turned round (nothing, at first), cur is the next node to turn, and nxt holds on to the rest of the list. Each pass saves cur's next in nxt, points cur back at prev, then moves prev and cur one node along.

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

head = Node(1, Node(2, Node(3, None)))
head = reverse(head)
node = head
while node is not None:
    print(node.value)
    node = node.next

Each pass turns one arrow round and does a fixed amount of work, so reversing n nodes is O(n) time, with three extra names whatever n is: O(1) extra memory. No value is copied and no node moves; only the arrows change direction.

The loop also shows the right way to go through a list: one pointer, stepped along, visiting each node once. Asking for positions by index is the wrong way, because each request starts again at head.

The same walk hides inside the O(1) that tables of costs give for inserting into a list.

Cheap ends make a linked list a natural queue: enqueue inserts at the tail and dequeue deletes at the head, and in the second list above, neither visited a node. Unlike the ring buffer in stacks and queues, it never fills up and never has to grow, because each value gets a node of its own. The cost is memory: every value carries a pointer, 8 bytes on a 64-bit machine, and every node is a separate allocation with its own overhead. Which end does which job matters, though.

A doubly linked list pays for that with a second pointer in every node, and with twice the pointer writes for each change: four to link a node in, two to unlink one. In return, any node you hold can be unlinked in O(1), and the list can be walked in both directions. Java's LinkedList is doubly linked, and Python's collections.deque is a doubly linked list of blocks of values.

One cost never shows up in big-O. The processor fetches memory in small blocks, so reading one array value brings its neighbours along for free. A list's nodes can be anywhere, so each hop can be a fresh trip to memory. Walking a list and scanning an array are both O(n), but the array usually wins by a wide margin, which is why most code reaches for an array first and keeps linked lists for when it really does splice in the middle.

Linked lists turn up most often as a part inside other structures. A hash table that resolves collisions by chaining, as Java's HashMap does, keeps the keys that land in one bucket in a short linked list. A graph's adjacency list can keep each vertex's neighbours in one. An LRU cache keeps its entries in a doubly linked list and finds each entry's node through a hash map, so it can unlink any entry in O(1) (the caching lesson shows it at work), and a database's B+ tree links its leaves so a range scan can walk along them (see storage engines).

• A linked list is a chain of nodes, each a value and a next pointer, reached through head. The nodes can be anywhere in memory.
• Inserting or deleting right after a node you hold rewires one or two pointers: O(1). Write the new node's next first, so the rest of the list stays reachable.
• Reaching index i, or searching, walks from head: O(n). There is no address formula, and scattered nodes make each hop slower than a step along an array.
• head and tail make adding at either end O(1), so a list can back a queue: enqueue at the tail, dequeue at the head. Removing the tail is O(n) unless the list is doubly linked.
• Reversing in place turns each arrow round in one pass, saving next before overwriting it: O(n) time, O(1) extra memory.
• Next: hash tables, which chain colliding keys in short linked lists, tries, where a node can have a next pointer for every letter, and representing graphs with adjacency lists. Practise with Reverse a Linked List (write it without looking back), Merge Two Sorted Linked Lists and Remove the Nth Node from the End, or open the linked list visualiser to try more operations.