Circular lists

Point the last node back at the first, and a list has no end. Watch the tail arrow, then two markers racing round.

⋯38struct node *insert_front(struct node *tail, int key)39{40    struct node *n = malloc(sizeof *n);41    if (n == NULL)42        exit(1);43    n->key = key;44    if (tail == NULL) {45        n->next = n;46        return n;47    }48    n->next = tail->next;49    tail->next = n;50    return tail;51}⋯79bool has_cycle(const struct node *head)80{81    const struct node *slow = head;82    const struct node *fast = head;83    while (fast != NULL && fast->next != NULL) {84        slow = slow->next;85        fast = fast->next->next;86        floyd_steps++;87        if (slow == fast)88            return true;89    }90    return false;91}⋯93int main(void)94{95    struct node *tail = NULL;96    tail = insert_back(tail, 2);97    tail = insert_back(tail, 3);98    tail = insert_back(tail, 4);99    tail = insert_front(tail, 1);100    tail = insert_back(tail, 5);101    print_ring(tail);102    serve(tail, 7);103    bool loops = has_cycle(tail->next);104    printf("loops %d after %d steps\n", loops, floyd_steps);105    struct node *head = tail->next;106    tail->next = NULL;107    free_list(head);108    return 0;109}

A ring kept by its tail

In a circular list the last node’s next is not NULL: it holds the first node’s address. The nodes form a ring, and any node can reach every other by following next.

Which node should the program hold? Holding the first makes the front cheap and the back a walk. Hold the last instead, the tail, and tail->next is the first. Both ends are one step away. That is why ring.c keeps only tail, and an empty ring is tail holding NULL.

Watch the insertions in the clip. insert_front puts the new node straight after the tail:

• Line 48, n->next = tail->next;, points the new node at the head.
• Line 49, tail->next = n;, points the tail at the new node, which is now the head.

It is the insertion from Singly linked lists, after the node tail holds: the new node’s link first, then the old one. insert_back is the same, then one more line: return tail->next; moves tail onto the new node, so it becomes the last instead of the first. The ring of one node is the special case: 2 is alone, so its next points at 2 itself (line 45).

After 2, 3 and 4 go in at the back, insert_front(tail, 1) puts 1 after the tail, 4, and tail stays on 4: tail->next is the 1 node at 0x1060, the new head. Then 5 goes in at the back. The ring is 1 → 2 → 3 → 4 → 5 → 1, with tail on 5 at 0x1080.

The code and its cost

Walking once round

void print_ring(const struct node *tail)
{
    const struct node *p = tail->next;
    do {
        printf("%d ", p->key);
        p = p->next;
    } while (p != tail->next);
    printf("\n");
}

There is no NULL to stop at. A walk of a ring stops when it is back where it started: p starts on the head, and the loop ends when p is the head again. The test comes at the bottom, do … while, so that the body runs once before it: with a test at the top, p would be on the head before the first key was printed, and the loop would print nothing. A ring of one node prints its one key. print_ring needs a ring with at least one node, since it reads tail->next at once.

Going round and round

void serve(const struct node *tail, int turns)
{
    const struct node *p = tail->next;
    for (int t = 0; t < turns; t++) {
        printf("%d ", p->key);
        p = p->next;
    }
    printf("\n");
}

Here the walk does not stop at the head. After 5, p moves on to 1, and the seven turns print 1 2 3 4 5 1 2 . Taking turns this way, one each and back to the start, is called round-robin: no pointer is ever reset, because the ring has no end to fall off.

Does a list loop at all?

A list that should end in NULL can loop by mistake, when some next field points back into the list. A walk on it never ends. To find out, without marking any node, has_cycle sends two pointers from the head: slow moves one node a step, fast moves two.

bool has_cycle(const struct node *head)
{
    const struct node *slow = head;
    const struct node *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        floyd_steps++;
        if (slow == fast)
            return true;
    }
    return false;
}

If the list ends, fast reaches NULL first and the answer is false. If it loops, both pointers end up going round the loop. From then on, each step moves fast two nodes and slow one, so the distance from fast round to slow falls by exactly one. On the ring of five it goes 4, 3, 2, 1, 0, and at 0 they are on the same node. Fast cannot jump over slow: to pass it, the gap would have to go from 1 to below 0, and it can only fall to 0.

On the ring of five, both start on 1. After k steps slow is k nodes on and fast 2k, so fast is k nodes ahead, and they are on the same node when k is a multiple of 5. Step 5: both on 1. The output is loops 1 after 5 steps. The method is often called Floyd’s cycle test.

The middle of a list

The same pair finds the middle of a list that ends. Run the loop without the test for meeting: when fast stops, at the last node or at NULL, slow has moved half as far. That is one walk instead of two (one to count, one to go halfway).

What it costs

Here n is the number of nodes. Inserting at either end is a fixed few steps, because tail and tail->next are both at hand. Walking round once is n steps. On a list of n nodes that ends, fast reaches the end in about n/2 steps; on one that loops, slow reaches the loop before the gap can close, and the two meet within n steps. Either way has_cycle needs only its two pointers of extra memory.

Cutting the ring before freeing it

free_list stops at NULL, and a ring has none. So main cuts it first: head = tail->next; keeps the first node’s address, and tail->next = NULL; makes 5 the end. On the uncut ring, free_list would free 1 to 5 and then read 1’s next from a node it had already freed, a use after free. Memory errors (2.5) has more of these.

Running it yourself

The full program, ring.c, starts with the list helpers from Removing from a linked list, then the counter floyd_steps and the functions above. Build and run it with:

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

It prints 1 2 3 4 5 , 1 2 3 4 5 1 2 and loops 1 after 5 steps.

Worked example

A loop that does not start at the head. The list is 1 → 2 → 3 → 4 → 5 → 6, and 6’s next points back at 3. slow and fast start on 1:

At step 3, fast has gone 5 → 6 → 3, round the loop, and is behind slow. At step 4 they meet on 5, after 4 steps.

The middle. On 1 to 7, slow and fast go (2, 3), (3, 5), (4, 7); fast’s next is NULL, so the loop stops with slow on 4. On 1 to 6 they go (2, 3), (3, 5), (4, NULL): slow stops on 4, the second of the two middles, 3 and 4.

Round-robin. Serving a ring of 5 tasks for 1,000 turns visits each task 200 times, in the same order every round, and p is never reset.

Where it’s used

Scheduling. An operating system that gives tasks turns on the processor, one slice each, can keep the ready tasks on a ring and simply move on to the next.

Turns. Players taking turns in a game, round and round, are a ring; a player who leaves is unlinked as in Removing from a linked list.

Playlists. A playlist set to repeat goes from its last track back to its first.

Checking structures. Slow and fast pointers check a linked structure for an accidental loop, a bug that would otherwise hang any walk over it. Doubly linked lists (7.6) close a ring of their own, and Circular queues (9.2) build a ring in an array.

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.