Doubly Linked Lists and What the Back Reference Buys

A doubly linked list gives every node a second reference, to the node before it, so a node can be unlinked knowing only the node itself, and the list can be walked from either end. This card covers what that reference makes O(1), what it costs and what it leaves O(n).

A music player's queue holds a reference to every song's node, and the listener removes one. In a singly linked list, where each node knows only the next, unlinking a node means changing the next of the node before it, and the only way to find that node is to walk from the head, which is O(n).

In the doubly linked list 3 7 5, each node has prev as well as next. The first node's prev and the last node's next are null, the marker for no node.

null <- [3] <-> [7] <-> [5] -> null

Removing the 7, given only its node, takes two changes: the node before it skips forward to the 5, and the node after it skips back to the 3. A run then removed the 5, the tail.

The run printed the list from both ends after each removal, and counted two changed references each time:

start:
head -> [3] -> [7] -> [5] -> null
tail -> [5] -> [7] -> [3] -> null

remove node 7, references changed: 2
head -> [3] -> [5] -> null
tail -> [5] -> [3] -> null

remove node 5, the tail, references changed: 2
head -> [3] -> null
tail -> [3] -> null

Each removal reads both neighbours from the node itself, so it does a fixed amount of work at any length. Where a neighbour is missing, the list's head or tail takes its place, which is why the same two changes handle the first and the last node. In general, a doubly linked list makes every change at a node you hold O(1): deleting it, inserting before it, inserting after it.

The price is one more reference in every node, so the list takes more memory, and two references to keep in step on every insert and delete, with twice the chances to leave the directions disagreeing.

The back reference does not make search faster. Finding the node that holds a value still checks nodes one at a time; starting from both ends at once halves the steps at best, and half of n is still O(n).

Choose the doubly linked list when the program already holds the nodes it changes and removes them from anywhere, as a cache that moves each entry it reads to the front does. When the program only adds and removes at the front, the singly linked list does the job with less memory.