Linked Lists Explained with Real Examples from the Linux Kernel

In the last post on queues, linked lists kept showing up. Wait queues were built from one, and the runqueue was 140 of them. This time we look at the linked list properly. It is one of the most used structures in the Linux kernel.

Let's write a small one in C first, then see how the kernel does it.

What is a linked list?

Think of a treasure hunt. Each clue tells you where the next one is. You can't jump to clue five. You start at the first and follow the chain.

A linked list works the same way. It is a chain of nodes. Each node holds some data and a pointer to the next node. The last one points to NULL.

There are two common kinds:

• In a singly linked list, each node points only to the next one
• In a doubly linked list, each node points to the next one and the one before it

The good part is that adding or removing a node is cheap once you are at the right spot. You change a pointer or two and nothing moves. In an array, adding in the middle means shifting everything after it.

The bad part is search. There is no index, so to find 42 you walk from the start and check each node.

A tiny linked list in C

Here is a small singly linked list of integers.

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

struct node {
    int data;
    struct node *next;
};

struct node *head = NULL;     /* NULL means the list is empty */

void push_front(int x) {
    struct node *n = malloc(sizeof *n);
    if (!n) return;           /* out of memory, so we stop */
    n->data = x;
    n->next = head;           /* new node points to the old first node */
    head = n;                 /* and becomes the new first node */
}

void delete_value(int x) {
    struct node **pp = &head;
    while (*pp && (*pp)->data != x)
        pp = &(*pp)->next;    /* walk until we find x */
    if (*pp) {
        struct node *gone = *pp;
        *pp = gone->next;     /* skip over the node */
        free(gone);
    }
}

void print_list(void) {
    for (struct node *p = head; p; p = p->next)
        printf("%d -> ", p->data);
    printf("NULL\n");
}

Adding at the front takes the same short time no matter how long the list is. We make one node, change two pointers, and never look at the rest. That is why it is O(1).

Deleting by value has to walk first, so it gets slower as the list grows. The pointer to a pointer, pp, lets the same code remove the first node or a middle one.

Doubly linked lists and the kernel's list_head

A doubly linked list adds a prev pointer to each node. It costs a bit more memory, but you can walk both ways and remove a node without hunting for the one before it.

The Linux kernel uses doubly linked lists everywhere, but it does not write a new list for each kind of data. It has one generic struct called list_head with only two fields, next and prev. No data at all.

The trick is that you put a list_head inside your own struct. The list does not hold your data. Your data holds the list.

A few things follow from this:

• The lists are circular. An empty list is just a head whose next and prev both point back to itself.
• The pointers point to other list_head fields, not to the start of the bigger struct. So when you are at a node, you need a way to get back to the struct around it.
• The kernel helper list_entry does that. It knows how far the list_head field sits from the start of the struct and subtracts that distance from the pointer. This idea is usually called "container of".
• Because every list looks the same, the kernel needs only one set of helpers to add, delete, and walk. Every subsystem reuses them instead of writing its own.

Where the Linux kernel uses linked lists

The examples below are from the Linux 2.6 kernel. Newer kernels have changed some details, but the ideas are still there.

The process list

Every process is linked into one big list through a list_head field called tasks in its descriptor. The head is init_task, the descriptor of the very first process.

To visit every process, the kernel has a macro called for_each_process. It starts at init_task, follows next, and stops when it comes back around. That stop rule works because the list is circular.

The runqueue

In Linux 2.6 each CPU has 140 lists, one per priority, and each is a plain list_head list. When a process becomes ready, enqueue_task() adds it to the tail of the list for its priority. To pick the next process, the scheduler finds the first non-empty list and takes the node at its front, using list_entry to get back the process.

Wait queues

Wait queues are also built on list_head. Each sleeper is a small entry in the list, and the head carries a lock. Exclusive sleepers go at the tail so the kernel can wake just one. Adding at the tail is cheap because the head's prev points straight at the last entry.

Hash tables and hlist

Hash tables have many buckets, and most are empty or short. A two-pointer head for each would waste memory. So the kernel has a lighter hlist. Its head, hlist_head, is a single pointer, and the list is not circular. You lose quick access to the tail, which a bucket rarely needs. The PID lookup table uses it.

Everyday uses

You meet linked lists outside the kernel too:

• A music playlist where "next" and "previous" move you along a chain
• Undo history in an editor, where each change points back to the one before
• Browser back and forward history, which behaves like a doubly linked chain
• Free block lists in memory allocators, where each free block points to the next free one

List or array?

Use an array when you read by position a lot, like "give me item 500". An array gets there in one step, and its items sit together in memory, which makes walking fast on real hardware.

Use a linked list when you add and remove items often, especially in the middle or at the front, and you already have a pointer to the spot. A list grows one node at a time, so you never guess a size up front. The price is extra memory for pointers and slow search.

Try it yourself

1. Add a push_back() function to the code above. Then keep a tail pointer so it runs in O(1).
2. Write a function that reverses the list in place, by changing pointers only.
3. Change the list to a doubly linked one, and write a delete that takes a node pointer instead of a value.

What comes next

Next in the series is the hash table. The hlist we just saw will make more sense once we look at how buckets work. If you'd like to build these structures yourself and watch them run, our C and data structures course goes through them one step at a time.