Reversing a list

To reverse a chain, nothing has to move: every arrow turns round. Watch the three tags, and the moment only next knows the way on.

⋯36struct node *reverse(struct node *head)37{38    struct node *prev = NULL;39    struct node *cur = head;40    while (cur != NULL) {41        struct node *next = cur->next;42        cur->next = prev;43        prev = cur;44        cur = next;45    }46    return prev;47}⋯67int main(void)68{69    struct node *head = NULL;70    head = push_front(head, 40);71    head = push_front(head, 30);72    head = push_front(head, 20);73    head = push_front(head, 10);74    head = reverse(head);75    print_list(head);76    head = reverse_rec(head);77    print_list(head);78    print_backwards(head);79    printf("\n");80    free_list(head);81    return 0;82}

Turning the arrows

The list is 10, 20, 30, 40, made by four calls of push_front: head holds 0x1060, the 10 node, and 40’s next is NULL. Reversed, it should read 40, 30, 20, 10. The nodes can stay where they are. What has to change is every next field: each node should point at the node that used to be behind it, and the first node, 10, should point at NULL.

reverse does this in one walk:

struct node *reverse(struct node *head)
{
    struct node *prev = NULL;
    struct node *cur = head;
    while (cur != NULL) {
        struct node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

cur is the node being turned. prev is the node behind it, already turned, or NULL at the start. Each turn of the loop runs four assignments:

1. next = cur->next saves the way forward.
2. cur->next = prev turns cur’s arrow round, to point behind.
3. prev = cur moves prev up.
4. cur = next moves cur on.

Here is the clip, turn by turn. Each row shows the boxes after the turn:

After turn 4, cur is NULL and the loop stops. prev holds 0x1000, the old last node, which is now the first; reverse returns it and main stores it in head. The list reads 40, 30, 20, 10, and every node is still at the address it was given.

Watch the moment just after line 42 runs, in any turn. cur’s arrow now points behind, so the node ahead is no longer reached through cur. For that moment only next holds the way forward. That is why next is saved first: line 41 copies the address before line 42 overwrites the only field that held it.

The code and its cost

Why three pointers

Two pointers are not enough. Turning cur’s arrow needs prev, the node to point at. And once the arrow is turned, the rest of the list is reached only through the address saved before the turn: that is next. Drop next, and the rest of the list is lost at the first turn; the worked example shows what that looks like.

What it costs

Here n is the number of nodes. The loop makes one turn per node, n turns, with four assignments in each. It makes no new nodes and needs only the three pointers, whatever the length: a fixed amount of extra memory, O(1) in the notation of Time and space complexity (3.3).

The recursive version

Reversing can also be written as a function that calls itself:

struct node *reverse_rec(struct node *head)
{
    if (head == NULL || head->next == NULL)
        return head;
    struct node *rest = reverse_rec(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

Read it as: reverse everything after head; the node after head is now the last node of that reversed part, so make it point back at head; then head is the end, for now. reverse.c calls it on the reversed list, 40, 30, 20, 10, and turns it back:

Four calls are open at once at the deepest point, and each return turns one arrow round. Every call returns rest, 0x1060, so main gets the new first node, 10, and the list reads 10, 20, 30, 40 again.

The cost is the same n steps, but each call takes its own frame on the stack until the deepest one returns: n frames at once. In this build, a frame of reverse_rec is 48 bytes, so a list of 1,000,000 nodes would need about 48 MB of stack, and a program’s stack on this platform is usually 8 MB. Recursion (4.1) shows what happens when the stack runs out. The loop has no such limit.

Printing backwards without changing anything

void print_backwards(const struct node *p)
{
    if (p == NULL)
        return;
    print_backwards(p->next);
    printf("%d ", p->key);
}

Each call prints the rest of the list first, then its own key. On 10, 20, 30, 40 it prints 40 30 20 10 , and no next field is written: the const says so. It makes 5 calls, one per node and the last with p NULL.

Running it yourself

The code pane shows reverse and main. The full program, reverse.c, starts with the list helpers from Removing from a linked list and has reverse_rec and print_backwards after reverse. Build and run it with:

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

It prints 40 30 20 10 , then 10 20 30 40 , then 40 30 20 10 .

Worked example

Swap the first two lines of the loop. Write cur->next = prev; before struct node *next = cur->next;. On the first turn cur is 10 and prev is NULL: 10’s arrow turns to NULL first, so next reads NULL from it. prev becomes 10, cur becomes NULL, and the loop ends after one turn. reverse returns the 10 node alone, and the program prints 10 three times.

20, 30 and 40 are still on the heap, but nothing leads to them. Built with the address sanitiser, the run ends with a report of one direct leak of 16 bytes, the 20 node, which no pointer reaches, and two indirect leaks of 16 bytes, 30 and 40, which are reached only from lost nodes.

Reverse 5 → 8 → 2 by hand. Start with prev NULL and cur on 5:

reverse returns the 2 node, and the list is 2 → 8 → 5.

A list of 1,000. One turn per node: 1,000 turns, and with four assignments in each, 4,000 assignments, plus the two before the loop. The recursive version makes 1,000 calls, all open at once at the deepest point.

Where it’s used

Building in the wrong order. Putting a node at the front of a list is cheap and putting it at the end is not, so a program often builds a list back to front and reverses it once at the end.

Undo. An editor’s undo history kept as a list has the newest change first; replaying the changes from the oldest means walking it reversed.

Big numbers. A number too large for any C type can be kept as a list of digits, lowest digit first, so that adding two numbers walks both lists from the units up; printing it means reversing the list or printing it backwards.

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.