Lesson 12 · Linear structures

Circular Linked Lists

A circular linked list forms a closed loop. The last node's pointer, instead of being null, points back to the first node. This structure is ideal for continuous round-robin processing without ever reaching an 'end'.

Closing the Loop

In a standard list, traversal stops when current.next == null. In a circular linked list, the tail node points directly to the head node.

You can implement this as a singly or doubly linked circular list. To traverse the entire ring once, you save a reference to the starting node and loop until current.next == start.

Tail points back to Head
No null pointers exist in the loop
Must be careful to avoid infinite loops during search

The Tail Pointer Advantage

When managing a circular list, you often only keep a reference to the tail node, rather than the head.

Because tail.next is the head, possessing the tail pointer gives you instant O(1) access to both the very end and the very beginning of the list, making insertions at both ends extremely fast.

Track the tail instead of the head
tail.next is always the head
O(1) insertions at both front and back

Key reference

Terms, operations, and practical uses

Topology

Ring StructureA linked list that forms a closed loop, where the final node connects back to the first node.
No Null PointersA properly formed circular list never contains a null reference; traversal can continue infinitely.
Tail TrackingKeeping a reference to the tail instead of the head, because tail.next provides instant access to the head.

Traversal mechanics

Starting ReferenceTo traverse a circular list exactly once, you must save the start node and stop when current.next equals the start node.
Infinite LoopsA common bug if a stopping condition is not correctly implemented when searching for an element.
Round-RobinContinuously cycling through nodes, giving each a 'turn' before moving to the next.

Applications

CPU SchedulingGiving multiple processes a tiny slice of CPU time in a repeating circle to simulate multitasking.
Josephus ProblemA mathematical puzzle where every k-th person in a circle is eliminated until one survives.
Multiplayer TurnsManaging player turns in a board game, looping back to Player 1 after the last player finishes.

Code example

Traversing a Circular Linked List

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# Setup A -> B -> C -> A
a = Node("A")
b = Node("B")
c = Node("C")
a.next = b
b.next = c
c.next = a

start = a
current = a
while True:
    print(current.val)
    current = current.next
    if current == start:
        break

#include <iostream>
using namespace std;

struct Node {
    string val;
    Node* next;
    Node(string x) : val(x), next(NULL) {}
};

int main() {
    Node* a = new Node("A");
    Node* b = new Node("B");
    Node* c = new Node("C");
    a->next = b; b->next = c; c->next = a;

    Node* start = a;
    Node* current = a;
    do {
        current = current->next;
    } while (current != start);
    return 0;
}

class Main {
    static class Node {
        String val;
        Node next;
        Node(String x) { val = x; }
    }
    public static void main(String[] args) {
        Node a = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        a.next = b; b.next = c; c.next = a;

        Node start = a;
        Node current = a;
        do {
            current = current.next;
        } while (current != start);
    }
}

InputRing: A -> B -> C -> A. Print nodes once.

Output

A
B
C

Example

Run the example step by step

Output

Round-Robin Scheduling

Circular lists model real-world cycles perfectly. An operating system might use a circular list to manage processes in a Round-Robin CPU scheduler.

The CPU executes the current node, then simply moves current = current.next to give the next process a turn, continuously looping through the ring forever.

Ideal for turn-based multiplayer games
Used in CPU time-slicing
Naturally models cyclic buffers

The Josephus Problem

A famous algorithmic puzzle that perfectly utilizes a circular linked list is the Josephus Problem: people stand in a circle and every k-th person is removed until one survives.

A circular linked list allows you to easily step k times and delete a node, continuing the circle effortlessly as it shrinks down to a single remaining node.

Classic mathematical elimination game
Nodes are removed while traversing continuously
List automatically shrinks while maintaining the circle