Circular Linked Lists

Definition and Invariant

A circular linked list is a linked list in which the last node's next field, instead of holding the null sentinel, points back to a designated start node. The chain becomes a ring.

Formally, for a circular list of size $n$ with nodes $v_0, v_1, \dots, v_{n-1}$:

$v_i.\text{next} = v_{(i+1) \bmod n}, \quad 0 \le i < n.$

That single change of the modular index is the entire definition. The structural invariant is that starting from any node and following $\text{next}^n$ times returns you to the same node. There is no terminator—no None, no NULL—and asking “is this the last node?” only makes sense relative to a chosen start.

• Singly-circular: one next pointer per node, ring oriented in one direction.
• Doubly-circular: every node holds prev and next, with $\text{tail.next} = \text{head}$ and $\text{head.prev} = \text{tail}$. The Linux kernel's struct list_head is the canonical example.

Why a Cycle on Purpose?

A circular list is what you reach for when the problem is itself cyclic: there is no “first” or “last,” only a current cursor that keeps walking around forever. The pattern shows up in:

In every case the key affordance is “given any node, advance once and you have the next thing to do,” with no special case at the boundary. The cycle removes a special case rather than adding one.

The Tail-Pointer-as-Handle Idiom

In a non-circular list you usually keep a head pointer and, if you care about $O(1)$ append, also a tail pointer. In a circular list, holding only the tail is strictly better:

1. Head is one hop away. By the cyclic invariant, tail.next is the head. So $O(1)$ head access is free.
2. Append is O(1). The tail is in your hand; just splice a new node between tail and tail.next, then move tail.
3. Prepend is O(1). Same splice, but don't move the tail—the new node simply becomes the new head.
4. Delete head is O(1). Rewrite tail.next to skip the old head.
5. One pointer of state, two endpoints accessible. Half the bookkeeping, no consistency bugs between separate head/tail pointers.

Traversal Without a None Terminator

The first time you write a loop over a circular list, your reflex—while p is not None—is now a bug. There is no None; the loop runs forever. The canonical idiom is to remember the start node and break when you wrap:

1# WRONG: infinite loop in a circular list.
2p = head
3while p is not None:        # condition never becomes True
4    visit(p.value)
5    p = p.next
6
7# RIGHT: stop when we come full circle.
8start = head
9p = start
10while True:
11    visit(p.value)
12    p = p.next
13    if p is start:
14        break               # we've visited every node exactly once

Two subtleties:

• Use identity (p is start), not equality (p == start). Two different nodes can carry the same value; you want the literal same object you started from.
• The do-while shape (visit then check) is correct precisely because visiting first guarantees the start node is processed exactly once. Reversing the order skips the start.

Bounded variant when the size is known:

1p = head
2for _ in range(n):           # exactly n hops, no identity check needed
3    visit(p.value)
4    p = p.next

This shape is preferable inside hot loops where the identity check would prevent loop-unrolling, and is the standard idiom inside ring-buffer code where $n$ is a power of two and the compiler can replace the increment with a bitwise & (mask).

Core Operations and Their Cost

Concatenation deserves a moment because it's the place circular lists shine over arrays and over non-circular linked lists alike:

1# Splice list B onto the end of list A — O(1), no walking required.
2def splice(A, B):
3    if A.tail is None: return B
4    if B.tail is None: return A
5    A_head = A.tail.next
6    B_head = B.tail.next
7    A.tail.next = B_head        # A's tail now leads into B's head
8    B.tail.next = A_head        # B's tail now closes the merged ring
9    A.tail = B.tail             # the tail of the merged ring is B's tail
10    A.size += B.size
11    return A

Two pointer rewrites, no copying, no walking either ring. With arrays this would be $O(|A| + |B|)$. With non-circular linked lists you'd also need to walk to A's tail unless you maintained one separately. Circular lists make “sew two rings into one” feel almost trivial.

Python Implementation

The class below maintains the singly-circular invariant, exposes append / prepend / delete-head / iterate, and includes a Josephus simulator that we'll dissect in the next section.

before: tail = None
after:  tail -> [v] -> (back to itself)

k=3, ring [1,2,3,4,5]:  prev=5 -> hops to 1 -> hops to 2  ⇒ doomed = prev.next = 3

1class Node:
2    __slots__ = ("value", "next")
3    def __init__(self, value, next=None):
4        self.value = value
5        self.next  = next
6
7class CircularLinkedList:
8    """Singly-circular list with a tail pointer.
9    Invariant: if size > 0, tail.next is the head."""
10    def __init__(self):
11        self.tail = None       # tail is None  <=>  list is empty
12        self.size = 0
13
14    def __len__(self):
15        return self.size
16
17    def head(self):
18        return self.tail.next if self.tail else None
19
20    def append(self, value):
21        node = Node(value)
22        if self.tail is None:
23            node.next = node                 # ring of one: points at itself
24            self.tail = node
25        else:
26            node.next = self.tail.next       # new node points to old head
27            self.tail.next = node            # old tail points to new node
28            self.tail = node                 # new node is now the tail
29        self.size += 1
30
31    def prepend(self, value):
32        node = Node(value)
33        if self.tail is None:
34            node.next = node
35            self.tail = node
36        else:
37            node.next = self.tail.next       # new node aims at the old head
38            self.tail.next = node            # tail now points at the new head
39        self.size += 1
40
41    def delete_head(self):
42        if self.tail is None:
43            raise IndexError("delete from empty list")
44        head = self.tail.next
45        if head is self.tail:                # the ring had exactly one node
46            self.tail = None
47        else:
48            self.tail.next = head.next       # bypass the old head
49        self.size -= 1
50        return head.value
51
52    def __iter__(self):
53        if self.tail is None:
54            return
55        start = self.tail.next               # remember the head
56        p = start
57        while True:
58            yield p.value
59            p = p.next
60            if p is start:                   # we've come full circle
61                break
62
63    def josephus(self, k):
64        """Eliminate every k-th node starting from the head; return the survivor's value."""
65        if self.tail is None or k < 1:
66            raise ValueError("non-empty list and k >= 1 required")
67        # Walk a 'prev' cursor: deleting a node is O(1) once prev is known.
68        prev = self.tail
69        while prev.next is not prev:         # more than one node remains
70            for _ in range(k - 1):           # advance k-1 hops to land on the doomed
71                prev = prev.next
72            doomed = prev.next
73            prev.next = doomed.next          # unlink the doomed node
74            if doomed is self.tail:          # keep tail invariant valid
75                self.tail = prev
76            self.size -= 1
77        return prev.value

C Implementation

The same idea in C, with explicit malloc / free. Notice how destruction has its own twist: you must break the cycle before walking, or the teardown loop never terminates.

Before: head -> n1 -> n2 -> ... -> tail -> head
After cut: head -> n1 -> n2 -> ... -> tail -> NULL

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct Node {
5    int value;
6    struct Node* next;
7} Node;
8
9typedef struct {
10    Node* tail;     /* tail->next is the head; NULL means empty */
11    int   size;
12} CList;
13
14void clist_init(CList* L) { L->tail = NULL; L->size = 0; }
15
16void clist_append(CList* L, int v) {
17    Node* n = (Node*) malloc(sizeof(Node));
18    n->value = v;
19    if (L->tail == NULL) {
20        n->next = n;            /* the ring of one points at itself */
21        L->tail = n;
22    } else {
23        n->next     = L->tail->next;   /* new node aims at old head */
24        L->tail->next = n;             /* old tail forwards to new   */
25        L->tail       = n;             /* new node IS the tail        */
26    }
27    L->size++;
28}
29
30int clist_josephus(CList* L, int k) {
31    Node* prev = L->tail;
32    while (prev->next != prev) {
33        for (int i = 0; i < k - 1; i++) prev = prev->next;
34        Node* doomed = prev->next;
35        prev->next   = doomed->next;
36        if (doomed == L->tail) L->tail = prev;
37        free(doomed);                   /* manual reclamation */
38        L->size--;
39    }
40    int survivor = prev->value;
41    free(prev);
42    L->tail = NULL;
43    L->size = 0;
44    return survivor;
45}
46
47void clist_destroy(CList* L) {
48    if (L->tail == NULL) return;
49    Node* p = L->tail->next;            /* start at the head */
50    L->tail->next = NULL;               /* BREAK THE CYCLE first! */
51    while (p != NULL) {
52        Node* doomed = p;
53        p = p->next;
54        free(doomed);
55    }
56    L->tail = NULL;
57    L->size = 0;
58}

Worked Example: The Josephus Problem

The Josephus problem is a 1st-century puzzle attributed to the historian Flavius Josephus: n people stand in a circle; starting from position 1, every k-th person is eliminated, and the count continues from the next position. Find the position of the last survivor.

Why is it the canonical worked example for circular lists? Because the data structure mirrors the problem statement perfectly: nodes are people, the cursor is the executioner, and elimination is a pointer rewrite. No translation tax.

The simulation

We track a predecessor cursor (rather than a current cursor) so that elimination is a single pointer rewrite without searching. At each step:

1. Hop $k - 1$ times to advance prev to the predecessor of the doomed node.
2. doomed = prev.next; prev.next = doomed.next unhooks the doomed node in $O(1)$.
3. If doomed happened to be the tail, set tail = prev to keep the invariant alive.
4. Repeat until the ring shrinks to one self-loop—the survivor.

Total work: $(n - 1)$ elimination rounds, each costing $O(k)$ hops, so simulation runs in $O(n \cdot k)$ time and $O(1)$ extra space.

Sanity check

For $(n, k) = (7, 3)$, eliminations occur in the order $3, 6, 2, 7, 5, 1$, leaving position $4$ as the survivor. Try it yourself in the playground below.

Doubly-Circular Variant

Add a prev field and the ring becomes doubly-circular. The structural invariant grows to two equations:

$v_i.\text{next} = v_{(i+1) \bmod n}, \qquad v_i.\text{prev} = v_{(i-1) \bmod n}.$

This is the data structure that powers an enormous amount of production systems software:

• Linux kernel: struct list_head is a 16-byte intrusive doubly-circular node embedded in every kernel object that needs to live on a list (tasks, file descriptors, inodes, free pages, …). The kernel uses a sentinel head node so that the empty list is “a node whosenext and prev point at itself.” Insertion and removal become four pointer writes with zero special cases.
• C++ STL: std::list is a doubly-circular list with a sentinel head, which is why end() returns a valid dereferenceable iterator (it points at the sentinel) and list::splice is $O(1)$.
• LRU caches: a hash map plus a doubly-circular list ordered by recency. “Touch” is unlink-and-prepend (constant time given the node pointer); “evict” is delete-tail (also constant time).
• Editor undo / redo rings: bounded history is naturally a doubly-circular buffer, with the oldest entry being overwritten when capacity is reached.

1/* Linux-style intrusive doubly-circular list (paraphrased). */
2struct list_head { struct list_head *next, *prev; };
3
4static inline void INIT_LIST_HEAD(struct list_head *h) {
5    h->next = h;                  /* empty == self-loop both ways */
6    h->prev = h;
7}
8
9static inline void list_add(struct list_head *new, struct list_head *head) {
10    /* insert 'new' between 'head' and 'head->next' — 4 writes, no branches */
11    new->next       = head->next;
12    new->prev       = head;
13    head->next->prev = new;
14    head->next       = new;
15}
16
17static inline void list_del(struct list_head *entry) {
18    entry->prev->next = entry->next;
19    entry->next->prev = entry->prev;
20    /* (no free here — the embedding object owns the storage) */
21}

Interactive: Circular List Lab

The lab below maintains a real singly-circular list. Each circle is a node; cyan arrows show next; the amber tail label points to tail; and toggling Doubly-circular reveals the violet prev arrows. Slide $k$, hit Run Josephus, and watch a ring of $n$ nodes melt down to one.

Things to try:

1. Start fresh, set $k = 3$, click Run Josephus. You should see eliminations in the order $3, 6, 2, 7, 5, 1$ with survivor $4$.
2. Click Rotate by 1 a few times. The ring is unchanged; only the chosen head moves. This is identically the operation a round-robin scheduler performs to advance to the next runnable thread.
3. Toggle Doubly-circular. Notice that the ring's topology hasn't changed—only its accessibility. prev is purely an algorithmic affordance, not a structural one.
4. Change $k$ to $1$. The eliminator stands still, killing every node in order—survivor is the last one inserted at the head. Edge case worth thinking about.

Where Circular Lists Live in Real Systems

Intended Cycle vs. Bug Cycle

Section 6.5 (next) introduces Floyd's tortoise-and-hare algorithm for detecting cycles in a list. It's critical to understand the conceptual difference between the cycle in this section and the cycle Floyd detects.

In practice, when you accept a list at an API boundary you can't always tell which kind of cycle you have. Defensive code does Floyd's detection first, then dispatches: ring ⇒ bounded traversal, no cycle ⇒ standard traversal, illegal cycle ⇒ reject.

Pitfalls

• Forgetting the self-loop on insert-into-empty. The very first node of a circular list must have node.next = node. Skip this and the next traversal walks off the end into uninitialized memory (C) or hits an AttributeError (Python).
• Using while p is not None. There is no None. The loop runs forever. Always remember a start node and break on identity.
• Off-by-one in Josephus. Whether the count includes the starting node or not changes the answer. The convention here (count starts at 1 from the current cursor) yields the classical sequence;range(k) instead of range(k - 1) shifts the survivor by one position.
• Not updating tail after removing tail. If the deletion happens to take out the tail itself, you must set tail = prev. Skip this and the next append splices into the middle of the ring; the symptom is silent data corruption, not a crash.
• Memory leaks under reference counting. Every node in a ring has refcount ≥ 1 from its predecessor, so dropping the only external handle does not free anything until the cycle collector runs. In real-time loops, break the cycle (tail.next = None) before letting the list go out of scope.
• Destroying a ring without breaking it first (C). A teardown loop expects a NULL terminator. Either rewrite the loop to count to $n$, or sever the ring once at the start and use the standard NULL-terminated walk.
• Treating the empty ring with a sentinel head as “empty” via size == 0. In the kernel list_head style, “empty” is head.next == &head. Write a helper (list_empty()) and use it everywhere; ad-hoc checks drift apart.

Quick Checks

The ring is the simplest non-trivial topology after the line. With the cyclic invariant in hand, you have a data structure that is the natural home for round-robin schedulers, ring buffers, and any process that repeats forever. The next section introduces Floyd's algorithm, which lets us tell the difference between a ring we built on purpose and a cycle that snuck in by accident.