Doubly and circular linked lists

Introduction

A singly linked node only knows the node after it. Two variations fix different weaknesses.

A plain linked list can only go forwards, and removing a node means first finding the one before it. Adding one more pointer to each node, or joining the two ends together, removes those limits at a small cost.

How it works

Circular linked lists

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
} Node;

Node *make_circle(int n) {
    Node *first = NULL, *last = NULL;
    for (int i = 1; i <= n; i++) {
        Node *p = malloc(sizeof(Node));
        p->value = i;
        if (first == NULL) first = p;
        else last->next = p;
        last = p;
    }
    last->next = first;   // close the circle
    return first;
}

int main(void) {
    Node *cur = make_circle(5);
    while (cur->next != cur) {
        Node *out = cur->next;   // the person after cur leaves
        cur->next = out->next;
        printf("%d leaves\n", out->value);
        free(out);
        cur = cur->next;
    }
    printf("%d is left\n", cur->value);
    free(cur);
    return 0;
}

In a circular list, the last node points back to the first instead of NULL, so you can go round and round. A loop over it must stop by itself; here it stops when a node points to itself, because it is the only one left.

The example solves the Josephus problem: 5 people stand in a circle; going round, every second person leaves. Who is left? Watch the arrow from cur move round the circle while the nodes disappear.

Syntax

typedef struct node {
    int value;
    struct node *prev, *next;
} Node;

n->prev->next = n->next;   // the node before skips n
n->next->prev = n->prev;   // the node after skips n

Example

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *prev, *next;
} Node;

Node *head = NULL, *tail = NULL;

void push_back(int value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->prev = tail;
    n->next = NULL;
    if (tail != NULL) tail->next = n;
    else head = n;
    tail = n;
}

void remove_node(Node *n) {
    if (n->prev != NULL) n->prev->next = n->next;
    else head = n->next;
    if (n->next != NULL) n->next->prev = n->prev;
    else tail = n->prev;
    free(n);
}

int main(void) {
    for (int v = 1; v <= 4; v++) push_back(v);
    remove_node(head->next);
    for (Node *p = tail; p != NULL; p = p->prev) printf("%d ", p->value);
    printf("\n");
    while (head != NULL) remove_node(head);
    return 0;
}

Each node has a prev pointer as well as next, so the list can be walked backwards from tail, and a node can be removed without searching for the node before it: n->prev is right there. Removing is O(1) once you hold a pointer to the node.

remove_node fixes two links, one on each side:

• the node before: n->prev->next = n->next (or move head, if n was first);
• the node after: n->next->prev = n->prev (or move tail, if n was last).

The price is one more pointer per node, and every insert and remove must keep both directions right.

Line by line

1. Each node has prev and next, and the global head and tail mark the two ends.
2. push_back links the new node after tail. If the list was empty, the new node is also the head.
3. remove_node fixes the node before: either its next, or head when there is no node before.
4. It then fixes the node after: either its prev, or tail when there is no node after.
5. main adds 1 to 4 and removes the second node with no search at all.
6. The printing loop starts at tail and follows prev, so the values come out backwards.
7. The last loop removes the head until the list is empty, which frees every node.

Expected result

4 3 1 

In the real world

A browser's history moves both backwards and forwards, and a music player can step either way through a playlist: both suit a doubly linked list. Circular lists suit anything that takes turns, such as an operating system giving each program a slice of time.

Common mistakes

• Updating only next in a doubly linked list: walking backwards then reaches a freed node.
• Walking a circular list with while (p != NULL): it never ends.
• Forgetting the special cases at head and tail.

Best practices

• Update both directions in one small function, so no caller can forget one.
• Check for NULL neighbours before following them.
• On a circular list, decide how the loop ends before writing it.

Summary

A doubly linked list stores a pointer each way, so it can walk backwards and remove a known node in O(1). A circular list joins the last node to the first, so its loops must stop by some test other than NULL.

Mark lesson complete