Circular linked list — applications: Visual walkthrough

This is the companion to the parent topic. If a symbol appears here you have not met, we stop and draw it.

Step 0 — What is a "node" and what is an "arrow"?

Look at the picture. Each cream box is a node. The value sits on the left; the burnt-orange arrow leaving the box is its next.

Figure — Circular linked list — applications

The teal curling arrow in the figure is the whole story: last.next = head.

Step 1 — Draw the circle we are counting around

We will not lean on the formula — we will walk the arrows instead, and only use the formula to check ourselves at the end.

Step 2 — How do we even move without falling off? (loop-safe traversal)

Formula Loop-safe traversal

p = start
do:
    visit(p)          # act on this node
    p = p.next        # hop one arrow forward
while p != start      # stop the instant we're home again

p :: our moving finger on the circle.
start :: the node we began on — our "home base".
p != start :: the only correct stop condition in a CLL; " $\neq =$ " means "is not the same box as".

The figure shows the finger p hopping arrow-to-arrow. Notice the green flags (visited) light up all five nodes before p lands back on home — proof the do-while covers everyone exactly once.

Step 3 — Why deleting a person is one line ( $O (1)$ )

The plum arrow is the old route through the victim; the burnt-orange arrow is the new shortcut prev.next → victim.next. The victim floats away, forgotten. Counting simply continues from prev.next.

Step 4 — Play the game: eliminate the 1st victim (person 2)

$prev 1 \to victim, count = k 2 ⟹ 1. next = 3$

Circle now: $1 \to 3 \to 4 \to 5 \to 1$ . Counting resumes from person 3.

The greyed box is person $2$ , spliced out. The new arrow $1 \to 3$ is highlighted.

Step 5 — Continue: eliminate person 4, then person 1

Two eliminations shown: person $4$ (top), then the wrap that catches person $1$ (the teal arc from $5$ back to $1$ ).

Step 6 — The final duel and the survivor

$3. next = 3 ⟹ one node loop ⟹ survivor = 3$

The lone node $3$ curling into itself — the same self-loop we insert as the first node of any CLL, now reached as the last survivor. The circle's life ends where it began: one box pointing at itself.

Step 7 — Edge & degenerate cases (never skip these)

The one-picture summary

The whole game on one canvas: the five-seat circle, the elimination order $2 \to 4 \to 1 \to 5$ drawn as fading plum arcs, and the surviving node $3$ glowing at the centre with its self-loop.

Recall Feynman: tell it to a 12-year-old

Five friends sit in a ring. You point at friend 1 and count "one, two" — friend 2 is out, so they leave and the ring closes up behind them. You keep counting from the next friend, always going round and round; when you reach the last seat you just keep going into the first seat like it's a racetrack, not a line. Every time you count to two, that friend leaves and the two friends beside them hold hands directly, skipping the gap. Do that over and over — 2 leaves, then 4, then 1 (that's the loop-around!), then 5 — until only friend 3 is left, holding their own hand in a tiny ring of one. The computer does the exact same thing: the "hold hands directly" is one arrow getting redrawn, and "keep going round" is the last arrow curling back to the first. That curling arrow is the entire magic of a circular linked list.

Recall Quick self-check

Why do we resume counting from prev.next after a delete? ::: Because victim.next (which prev now points to) is the very next living person, so counting continues seamlessly with no gap. For $n = 5, k = 2$ , who is the survivor and why? ::: Person 3 — eliminations run 2, 4, 1, 5; the wrap from 5 back to 1 (handled free by the circular arrow) is what leaves 3 last. What does p.next == p signal? ::: A one-node circle — the terminating state; that node is the survivor.

Related: Circular linked list — applications · Josephus Problem · Round-Robin Scheduling · Ring Buffer · Singly Linked List · Doubly Linked List · Queue · Fibonacci Heap