Doubly linked lists

Give each node a second arrow, back to the one before, and close the ring with a spare node. Watch 15 go in with four writes.

⋯9void list_init(struct dnode *s)10{11    s->prev = s;12    s->next = s;13}⋯26void insert_before(struct dnode *pos, struct dnode *n)27{28    n->prev = pos->prev;29    n->next = pos;30    pos->prev->next = n;31    pos->prev = n;32}33 34void unlink_node(struct dnode *n)35{36    n->prev->next = n->next;37    n->next->prev = n->prev;38}⋯65int main(void)66{67    struct dnode list;68    list_init(&list);69    struct dnode *a = new_dnode(10);70    insert_before(&list, a);71    struct dnode *b = new_dnode(20);72    insert_before(&list, b);73    struct dnode *c = new_dnode(30);74    insert_before(&list, c);75    insert_before(b, new_dnode(15));76    unlink_node(b);77    free(b);78    print_forward(&list);79    print_backward(&list);80    free_all(&list);81    return 0;82}

A node that knows its neighbours

A node of a singly linked list knows only the node after it. To remove a node, Removing from a linked list had to walk from the head to find the link pointing at it. Give each node a second pointer, to the node before, and that walk disappears:

struct dnode {
    int key;
    struct dnode *prev, *next;
};

key is at offset 0, then 4 bytes of padding, then prev at offset 8 and next at offset 16: sizeof (struct dnode) is 24. A list built from these nodes is doubly linked: forward by next, backward by prev.

dlist.c adds one more idea. The list is a ring, as in Circular lists, and the ring is closed by an extra node that holds no item: the sentinel. In main it is the local struct dnode list, a whole node in main’s frame, at 0x7fd8 in the picture. Its key is never written. The first item is list.next, the last is list.prev, and the last item’s next points back to the sentinel.

The code and its cost

The empty list

void list_init(struct dnode *s)
{
    s->prev = s;
    s->next = s;
}

An empty list is the sentinel pointing to itself both ways. After list_init(&list), list.prev and list.next both hold 0x7fd8, the sentinel’s own address. The sentinel is not the first item: it is there when the list is empty, and the walks below skip it.

Four writes, in order

void insert_before(struct dnode *pos, struct dnode *n)
{
    n->prev = pos->prev;
    n->next = pos;
    pos->prev->next = n;
    pos->prev = n;
}

insert_before puts n just before pos. Watch 15 go in before 20 in the clip:

• Line 28, n->prev = pos->prev;, points 15’s prev at 10, the node before 20.
• Line 29, n->next = pos;, points 15’s next at 20.
• Line 30, pos->prev->next = n;, swings 10’s next onto 15.
• Line 31, pos->prev = n;, swings 20’s prev onto 15.

The new node’s two pointers are set first. At that moment it is fully wired, and nothing in the list points to it yet. Then the two neighbours’ pointers swing onto it.

The order of the last two lines matters. Line 30 reaches 10 through pos->prev. Once line 31 has run, pos->prev is 15, so 10 can no longer be reached that way. The worked example below swaps them and shows the damage.

There is no if in insert_before. With the sentinel, every node has a node before it and a node after it, even in a list of one item, even in an empty list, where both are the sentinel. Inserting before the sentinel puts a node at the back: that is how main adds 10, 20 and 30, in that order. Inserting before list.next puts it at the front.

Unlinking by address

void unlink_node(struct dnode *n)
{
    n->prev->next = n->next;
    n->next->prev = n->prev;
}

To take 20 out, unlink_node needs only 20’s address. Its node already says who its neighbours are: line 36 points 15’s next past 20 to 30, and line 37 points 30’s prev back to 15. Two writes, whatever the length of the list, and no walk. 20’s own two fields still hold 15 and 30, drawn dashed once it is freed; nothing in the list leads to it any more, and free(b) gives it back.

The function is called unlink_node and not unlink, because the C library on these systems already has an unlink: it deletes a file.

Walking both ways

void print_forward(const struct dnode *s)
{
    for (const struct dnode *p = s->next; p != s; p = p->next)
        printf("%d ", p->key);
    printf("\n");
}

The walk starts at the first item, s->next, and stops when it is back at the sentinel. print_backward is the same with prev in place of next. The output is 10 15 30 and then 30 15 10 . On an empty list, s->next is the sentinel itself, so the loop never runs and the walk prints only the end of the line.

What it costs

Inserting before a node you hold, and unlinking a node you hold, are each a fixed number of writes: four and two. Finding a key still means a walk, up to n steps for a list of n items (all n when the key is last or absent).

The price is memory. A node here is 24 bytes, where the singly linked node of Removing from a linked list was 16. On this platform the C library spaces both at 32 bytes, so in the picture they take the same room.

Freeing the list

free_all walks from s->next, keeping each node’s next before it frees the node, and stops at the sentinel. Then it calls list_init(s), so the sentinel points to itself again and the list can be used once more. The sentinel itself is never freed: it was never allocated, and it goes away with main’s frame.

Running it yourself

The program is dlist.c: struct dnode, list_init, new_dnode, insert_before, unlink_node, the two walks, free_all and main. Build and run it with:

gcc -std=c11 -Wall -Wextra -pedantic dlist.c -o dlist
./dlist

It prints 10 15 30 and 30 15 10 .

Worked example

The last two lines swapped. Suppose insert_before ran pos->prev = n; before pos->prev->next = n;, again for 15 before 20. The first two lines point 15’s prev at 10 and its next at 20, as before. Then 20’s prev becomes 15. The last line follows pos->prev, which is now 15, and writes 15->next = 15. 15 points to itself, and 10 still points to 20. A forward walk prints 10 20 30: 15 is missing. A backward walk prints 30 20 15 10. The two directions no longer agree.

Pushing to the front. insert_before(list.next, n) puts n before the first item. On the empty list, list.next is the sentinel, so the same call works there too.

Moving a node to the front. A cache that keeps its most recent item first does this on every use: unlink_node(n), then insert_before(list.next, n). That is two writes and four, six in all, whatever the length of the list. Least-recently-used caches (20.1) are built on it.

The empty list. After list_init, print_forward prints a blank line: p starts at list.next, which is the sentinel, and the loop test fails at once.

Where it’s used

Caches. A least-recently-used cache keeps its items on a doubly linked list, most recent first, and moves an item to the front on every use, with the six writes above: LRU caches.

Operating systems. Kernels keep tasks, open files and many other objects on rings with a sentinel, because a task can then remove itself from a list knowing only its own node.

Undo and redo. An editor’s history can move back and forward one change at a time, by prev and by next.

Windows. The list of open windows, in the order they were last used, changes whenever one is brought to the front. Double-ended queues (9.3) are built the same way.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.