Circular linked list

A circular linked list is a Linked list where the last node’s next pointer wraps around to point at the first node, forming a closed ring instead of ending at NULL. Useful for round-robin processing, repeating sequences, and any scenario where there’s no natural “end.”

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

The struct is identical to a regular linked list. The difference is purely in the invariant: there’s no NULL terminator — every node points to another valid node.

Singly vs doubly circular

Two flavors:

• Singly circular: each node has only next. The last node’s next points to head.
• Doubly circular: each node has next and prev. The last next points to head; the head’s prev points to last. Forms a true bidirectional ring.

The doubly circular form is common in OS kernel data structures (Linux list_head is exactly this).

Operations

Traversal

Without a NULL sentinel, you need a different stopping condition. Common pattern: keep a pointer to the head, walk until you return to it.

void traverse(struct node *head) {
    if (head == NULL) return;
    struct node *current = head;
    do {
        printf("%d ", current->value);
        current = current->next;
    } while (current != head);
}

The do-while ensures the head is processed once even when there’s only one node (whose next points to itself).

Insertion

To insert at the front: link the new node into the cycle and update head.

void insertFront(struct node **head, int value) {
    struct node *new = malloc(sizeof(struct node));
    new->value = value;
    
    if (*head == NULL) {
        new->next = new;       // single node, points to itself
        *head = new;
        return;
    }
    
    // find the last node (the one whose next is head)
    struct node *last = *head;
    while (last->next != *head) last = last->next;
    
    new->next = *head;
    last->next = new;
    *head = new;
}

Walking to find the last node is $O(n)$ — annoying. To make insertion at the front $O(1)$, maintain a separate tail pointer instead. Or use a doubly-linked circular list, where head->prev is the last node directly.

Deletion

Similar care is needed: detach the node and ensure the cycle remains closed.

Use cases

Round-robin scheduling

Operating systems schedule processes by cycling through a list of ready processes, giving each a time slice. A circular list naturally represents this — after the last process, you go back to the first.

Repeating playback

A music player set to “repeat playlist” cycles through tracks endlessly. A circular list of tracks; the next-song pointer just follows next, naturally wrapping at the end.

Multiplayer games

Card games, board games where players take turns in a fixed order. After the last player’s turn, the next player is the first — circular list.

Buffer management

A circular buffer (ring buffer) is similar in spirit but typically uses an array with two indices (read and write) for efficiency.

Josephus problem

A classic computer-science puzzle: $n$ people in a circle, every $k$-th person is eliminated until one remains. Naturally modeled with a circular list — eliminate a node, advance, repeat.

Trade-offs vs regular linked lists

Pros:

• No NULL terminator to special-case at the end.
• Natural representation of cyclic data.
• Easy to “reset” by jumping back to head.

Cons:

• Traversal needs careful termination (don’t loop forever).
• Some operations are slightly trickier (insertion at front needs to know the last node).
• Bug risk: if you forget to maintain the cycle, you create a broken list — possibly with no NULL termination, infinite-looping the next traversal.

In context

Compared to other linked list variants:

• Regular Linked list: NULL-terminated, has a clear end.
• Doubly linked list: bidirectional, NULL-terminated.
• Circular linked list: no end, wraps around.
• Doubly-linked circular list: bidirectional + circular. The most flexible (and most common in low-level systems code).

For the basic linked-list operations and theory, see Linked list. For the doubly-linked variant that also supports backward traversal, see Doubly linked list.