Singly linked lists

An array keeps its items side by side. What if each item said where the next one is? Watch the arrows, not the row.

⋯19void insert_after(struct node *prev, int key)20{21    struct node *n = malloc(sizeof *n);22    if (n == NULL)23        exit(1);24    n->key = key;25    n->next = prev->next;26    prev->next = n;27}⋯47int main(void)48{49    struct node *head = NULL;50    head = push_front(head, 40);51    head = push_front(head, 20);52    head = push_front(head, 10);53    insert_after(head->next, 30);54    print_list(head, 6);55    free_list(head);56    return 0;57}

Nodes on the heap

Each item of the list is a node, a struct with two fields:

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

key is the value the list stores. next holds the address of the next node, so the struct holds a pointer to its own kind. From Structs (1.4): a struct’s fields sit in order, with padding where a field needs alignment. Here key takes 4 bytes, 4 bytes of padding follow so that next starts on a multiple of 8, and next takes 8. A node is 16 bytes.

From The heap: malloc and free (2.4): malloc(sizeof *n) finds 16 bytes on the heap and returns their address, or NULL when no memory is left; free gives a block back. And from Passing pointers to functions (2.2): n->key is the field key of the struct at the address in n, the same as (*n).key.

Now the clip. Each push_front makes one node and puts it in front of the list. The first makes 40 at 0x1000, the second 20 at 0x1020, the third 10 at 0x1040. After line 52 the list reads 10, 20, 40: start at the address in head, 0x1040, and follow each next.

The heap row shows the same nodes in address order: 40, 20, 10, left to right, because 40 was allocated first. So the list’s arrows jump right to left across the row. The list’s order is not the heap’s order. Nothing keeps the nodes side by side; the next fields alone decide the order.

head is not the first node either. It is an 8-byte pointer box in main’s frame, at 0x7fe8, holding the first node’s address. An empty list is head holding NULL, and the last node’s next is NULL.

Then insert_after(head->next, 30) puts 30 after 20. Watch the two lines that do it:

• Line 25, n->next = prev->next;, copies 20’s next, 0x1000, into the new node. For a moment two arrows point at 40.
• Line 26, prev->next = n;, writes 0x1060 into 20’s next. 20’s arrow swings onto the new node, and the list is 10, 20, 30, 40.

Last, print_list walks the list with a pointer p. p moves from node to node, and no arrow on the heap changes. The output is 10 20 30 40 .

Now a prediction, before you touch the switch. What if the two lines ran the other way round, prev->next = n; first? Which arrows would you see, and what would the walk print?

Set the switch to “swapped”. The replay starts just before line 25. First 20’s arrow swings to the new node, and nothing points at 40 any more: it greys. Then n->next = prev->next; reads 20’s next, which is now 0x1060, the new node’s own address. The new node points at itself, and the walk prints 10 20 30 30 30 30 .

The walk stops there only because print_list takes a limit, max, and prints at most 6 keys; without it, a list that loops would print for ever. The 40 node is still on the heap, but no pointer leads to it, so the program can never free it. Built with the address sanitiser, the swapped program reports a leak of 16 bytes in 1 object.

The code and its cost

Walking a list

print_list is the walk:

void print_list(const struct node *head, int max)
{
    for (const struct node *p = head; p != NULL && max > 0; p = p->next) {
        printf("%d ", p->key);
        max = max - 1;
    }
    printf("\n");
}

The const says that print_list only reads the nodes. p starts at the first node and stops at NULL. The step p = p->next writes a new address into p, the box in print_list’s frame, and into nothing else. A walk leaves the list as it found it. Without the limit, the loop is the usual walk, for (p = head; p != NULL; p = p->next).

Inserting at the front

struct node *push_front(struct node *head, int key)
{
    struct node *n = malloc(sizeof *n);
    if (n == NULL)
        exit(1);
    n->key = key;
    n->next = head;
    return n;
}

The new node points at the old first node, and becomes the first itself. push_front has its own copy of head, in its own frame at 0x7fd0, so writing to that copy would not change main’s head. It returns the new node’s address instead, and main stores it: head = push_front(head, 40);. If malloc finds no memory, the program stops with exit(1).

Inserting after a node

insert_after(prev, key) makes a node n the same way, then runs the two lines from the clip: n->next = prev->next;, then prev->next = n;. The order matters. The first line keeps the only record of where the rest of the list is, so it must copy that record before the second line overwrites it.

What it costs

Here n is the number of nodes in the list. Inserting after a node you already hold takes two pointer writes, plus the malloc and the key, however long the list is. Finding that node is the slow part: a list has no jump to its i-th node, so you walk from head, one step per node, up to n steps.

An array is the other way round. a[i] reaches any element in one step, but putting a new element at the front moves every element one place along. For a list of 1,000,000, that is 1,000,000 moves in the array and two pointer writes in the list.

Each node also pays for its link: 16 bytes for a 4-byte key on this platform.

Running it yourself

The code pane shows insert_after and main. The full program, list.c, is those with the three functions above and free_list, which gives every node back; Removing from a linked list (7.2) explains how it walks the list while freeing it. Build and run it with:

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

Worked example

Three nodes sit on the heap, and head holds 0x1000:

Read the list. Start at head: 0x1000 holds 5, and its next is 0x1040. 0x1040 holds 7, and its next is 0x1020. 0x1020 holds 9, and its next is NULL. So the list is 5, 7, 9, though the heap holds them 5, 9, 7.

Insert 8 after 7. insert_after gets prev = 0x1040, the node holding 7. Each line writes one box:

The list is now 5, 7, 8, 9. Only two next fields were written, and the nodes holding 5 and 9 were not touched.

The swapped order. Run line 26 first: it writes 0x1060 into 7’s next. Then line 25 copies 7’s next, now 0x1060, into the new node. 8 points to 8, and nothing leads to 9. A walk with a limit of 6 would print 5 7 8 8 8 8 .

The cost. Put a key at the front of a 1,000,000-element array, and 1,000,000 elements shift; at the front of a list it is two pointer writes. Put it after the 500,000th element: the list walks 499,999 steps from head to reach that node, then writes two pointers; the array shifts the 500,000 elements after it.

The replay below builds this list with the page’s own functions: push_front(NULL, 5), then insert_after(head, 9) and insert_after(head, 7), then insert_after(head->next, 8). Before you play it: why does 7 land between 5 and 9? (Because it goes in after the node head points to, 5, and takes 5’s old next, 9.)

⋯19void insert_after(struct node *prev, int key)20{21    struct node *n = malloc(sizeof *n);22    if (n == NULL)23        exit(1);24    n->key = key;25    n->next = prev->next;26    prev->next = n;27}⋯47int main(void)48{49    struct node *head = push_front(NULL, 5);50    insert_after(head, 9);51    insert_after(head, 7);52    insert_after(head->next, 8);53    print_list(head, 6);54    free_list(head);55    return 0;56}

Where it’s used

Memory allocators. An allocator keeps the blocks that programs have freed on linked lists, one list per block size, with each block’s next pointer stored inside the free block itself. The C library’s malloc on this platform does this for small blocks.

Waiting tasks. Operating systems keep the tasks that are waiting, for a lock or for a device, on linked lists, so that a task can join or leave the line in a few pointer writes.

Hash tables. A common hash table keeps a short linked list in each of its slots, holding the keys that land there; Hash tables with chaining (18.2) builds one.

Items that must not move. A node stays at its address while the list around it grows and shrinks, so other parts of a program can hold its address safely. An array that grows may have to move all its elements to a larger block.

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.