Circular Linked List, in depth: tail pointers, sentinel rings, the Josephus problem, round-robin and when a ring buffer is better

The shape and why the tail pointer matters

In a singly linked circular list every node has a value and a next pointer, and following next from any node visits every node once before returning. There is no node whose next is null, except in the degenerate sense that an empty list has no nodes at all. A list with one node points to itself, and that self-loop is the case most bugs forget.

The choice of which pointer to keep matters. If you keep only a head pointer, inserting at the back requires walking all the way round to find the last node, which is O(n). If you keep a tail pointer, the head is always tail.next, so you reach both ends in O(1). Inserting at the front and at the back become the same splice; the only difference is whether the tail moves afterwards. Removing the front is also O(1). Removing the back is still O(n) in a singly linked ring, because you need the node before the tail; a doubly linked ring fixes that.

A tail-pointer implementation

The implementation below keeps a tail pointer and a size. Every operation handles the empty and single-node cases explicitly, because those are where circular lists break.

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val):
        self.val = val
        self.next = self          # a lone node is a ring of one

class CircularList:
    def __init__(self):
        self.tail = None
        self.size = 0

    def push_front(self, val):
        node = Node(val)
        if self.tail is None:
            self.tail = node
        else:
            node.next = self.tail.next
            self.tail.next = node
        self.size += 1

    def push_back(self, val):
        self.push_front(val)
        self.tail = self.tail.next   # the new front becomes the new tail

    def pop_front(self):
        if self.tail is None:
            raise IndexError("pop from empty list")
        head = self.tail.next
        if head is self.tail:        # single node
            self.tail = None
        else:
            self.tail.next = head.next
        self.size -= 1
        return head.val

    def rotate(self, k=1):
        if self.tail is not None:
            for _ in range(k % self.size):
                self.tail = self.tail.next

    def remove(self, val):
        if self.tail is None:
            return False
        prev = self.tail
        for _ in range(self.size):
            cur = prev.next
            if cur.val == val:
                if cur is prev:      # removing the only node
                    self.tail = None
                else:
                    prev.next = cur.next
                    if cur is self.tail:
                        self.tail = prev
                self.size -= 1
                return True
            prev = cur
        return False

    def __iter__(self):
        if self.tail is None:
            return
        node = self.tail.next
        for _ in range(self.size):   # bounded: never loops forever
            yield node.val
            node = node.next

Notice the trick in push_back: insert at the front, then advance the tail by one, and the new node is now last. Notice also that iteration is bounded by the size rather than by a null check. A loop written as while node is not None never terminates on a ring, which is the single most common circular-list bug. If you do not track size, iterate with a do-while shape: visit the head, move on, and stop when you are back at the head.

Sentinel rings in the Linux style

The Linux kernel uses a circular doubly linked list with a sentinel, struct list_head, for almost every in-kernel collection. The sentinel is a node that holds no data; an empty list is a sentinel whose next and previous pointers point to itself. Because the ring always contains the sentinel, no operation needs a special case for empty or single-element lists. The lists are intrusive: the list_head is embedded inside the structure being listed, and the containing structure is recovered with pointer arithmetic, so adding an object to a list allocates nothing. A simplified version looks like this.

struct list_head { struct list_head *next, *prev; };

static inline void init_list(struct list_head *h) { h->next = h; h->prev = h; }

static inline void insert_between(struct list_head *n,
                                  struct list_head *prev, struct list_head *next) {
    next->prev = n;
    n->next = next;
    n->prev = prev;
    prev->next = n;
}

/* add after the sentinel (stack order) or before it (queue order) */
static inline void list_add(struct list_head *n, struct list_head *h)      { insert_between(n, h, h->next); }
static inline void list_add_tail(struct list_head *n, struct list_head *h) { insert_between(n, h->prev, h); }

static inline void list_del(struct list_head *e) {
    e->next->prev = e->prev;
    e->prev->next = e->next;
    e->next = e->prev = NULL;   /* poison so use-after-delete faults loudly */
}

#define for_each(pos, head) for (pos = (head)->next; pos != (head); pos = pos->next)

Deletion is O(1) given a pointer to the element, insertion at either end is O(1), and traversal stops when it returns to the sentinel. The kernel's real version writes poison values rather than null, adds debug checks and has RCU-safe variants for lock-free readers; the shape is the same. This structure is also the core of an O(1) LRU cache, where a hash map points into a circular doubly linked list, as shown in LRU cache design.

Worked example: the Josephus problem

The Josephus problem is the textbook use, and it shows both the strength and the limit of the structure. People numbered 1 to n stand in a circle. Starting from person 1, count k people and remove the k-th; continue counting from the next person; the last one standing survives. A circular list models this directly: rotate k - 1 steps, pop the front, repeat.

Work it through for n = 7 and k = 3. Counting 1, 2, 3 removes 3. Counting from 4 gives 4, 5, 6 and removes 6. Counting from 7 gives 7, 1, 2 and removes 2. Counting from 4 gives 4, 5, 7 and removes 7. Counting from 1 gives 1, 4, 5 and removes 5. Counting from 1 gives 1, 4, 1 and removes 1. Person 4 survives, and the removal order is 3, 6, 2, 7, 5, 1.

def josephus_sim(n, k):
    ring = CircularList()
    for i in range(1, n + 1):
        ring.push_back(i)
    order = []
    while ring.size > 1:
        ring.rotate(k - 1)            # move the k-th person to the front
        order.append(ring.pop_front())
    return ring.pop_front(), order    # O(n * k)

def josephus_formula(n, k):
    j = 0                             # survivor index for a circle of 1 (0-based)
    for m in range(2, n + 1):
        j = (j + k) % m
    return j + 1                      # O(n), no list at all

assert josephus_sim(7, 3) == (4, [3, 6, 2, 7, 5, 1])
assert josephus_formula(7, 3) == 4

The simulation costs O(nk) and gives the full elimination order. The recurrence J(1) = 0 and J(m) = (J(m - 1) + k) mod m gives only the survivor, in O(n) with no allocation. That is a general lesson: the circular list is the right model when you need the sequence of events, but once you need only a final answer, there is often an arithmetic shortcut.

Where circular lists are used

Where circular lists earn their place in real systems:

• Round-robin scheduling. Runnable tasks sit in a ring; the scheduler runs the head for a time slice and rotates. Adding a task is a splice before the head, and removing a blocked task is O(1) with a doubly linked ring. Classic operating system run queues and network packet schedulers that serve flows in turn use this shape.
• The CLOCK page-replacement algorithm. Pages sit in a circle with a reference bit. A hand sweeps round; a page whose bit is set gets the bit cleared and a second chance, and the first page found with a clear bit is evicted. It approximates LRU with one bit per page and is used, in variants, by real virtual memory and buffer cache systems. The circle may be a linked ring or an array with a wrapping index.
• Turn order and playlists. Players in a game, or a playlist on repeat, are a ring where the current position advances and members join or leave in the middle.
• Intrusive kernel and embedded collections. As above, a sentinel ring removes edge cases and allocation from hot paths.

Circular lists versus ring buffers

Many descriptions, including the page this article replaces, equate circular linked lists with ring buffers. They are different structures. A ring buffer is usually a fixed-size array with a read index and a write index that wrap around modulo the capacity. It has no pointers, never allocates after creation, and keeps elements contiguous, so iteration is cache-friendly and a single-producer, single-consumer version can be made lock-free with two atomic indices. That is why log buffers, audio buffers, network card descriptor rings and message queues use arrays, not linked nodes.

Rule of thumb: if the collection is a queue with a known bound, use an array ring. If members join and leave from arbitrary positions and you already hold pointers to them, use a circular linked list.

Failure modes

Most circular-list bugs come from a short list of mistakes.

• Infinite traversal. Looping until null. Guard: bound by size or stop on return to the head or sentinel.
• Single-node removal. Removing the only node and leaving the tail pointing to a freed node. Guard: test the empty and one-element cases for every operation.
• Removing the tail. Deleting the last node without moving the tail pointer back. Guard: check cur is tail in removal, as in the code above.
• Accidental rings. A bug that makes an ordinary list circular causes the same hang. Guard: in tests, run Floyd's tortoise-and-hare check described in Floyd cycle detection on lists that should be linear.
• Mutation during iteration. Deleting the current node while iterating loses the next pointer. Guard: save next before deleting, which is what the kernel's safe iteration macros do.
• Concurrency. Two threads splicing the same ring corrupt it silently. Guard: one lock per ring, or a published lock-free design; do not invent your own.

Costs and trade-offs

The trade-off is the usual one for linked structures: constant-time splicing and stable node addresses in exchange for a pointer or two per element, an allocation per insert unless the list is intrusive, and poor cache behaviour during traversal. On modern hardware a linear scan over a contiguous array of a few thousand elements often beats a linked traversal of the same length, so measure before choosing a linked ring for speed.

What to do next

• Implement the tail-pointer list above and write tests for empty, one-element and two-element lists for every operation.
• Implement the sentinel doubly linked ring and confirm that no operation needs an empty-list branch.
• Solve Josephus both ways and check the simulation against the recurrence for n up to 1,000.
• Build a CLOCK eviction cache with an array ring, then with a linked ring, and compare speed.
• Audit existing code for traversal loops that rely on reaching null.
• Before choosing a circular linked list, check whether a bounded array ring buffer meets the need.