Circular linked list — applications: Worked examples

Before we start, two words we'll reuse:

The scenario matrix

Every problem this topic can throw lives in one of these cells. The examples below are labelled with the cell they cover.

Cell	Case class	What makes it tricky
A	Empty list (0 nodes)	No head, no tail — the degenerate base case
B	Single node (1 node)	The node must point to itself; head = tail
C	Insert front / insert back	Must re-close the loop (`tail.next = head`)
D	Delete a middle node	Relink `prev.next = victim.next`, keep loop
E	Delete the head or the tail	The "first"/"last" label moves — special care
F	Traversal (count / print)	Stop at `p == start`, not at `null`; empty needs a pre-check
G	Wrap-around counting (Josephus)	Counting crosses the seam back to the start
H	Buffer overflow (ring buffer full)	Oldest data is overwritten when write meets read
I	Real-world word problem	Round-robin scheduling over several rounds
J	Exam twist / limiting value	k larger than n; k = 1; huge k modulo n

Prerequisites you may want open: Singly Linked List, Doubly Linked List, Queue.

Worked examples

Example 1 — The empty list (Cell A)

Worked example Insert into an empty CLL

We have an empty CLL: head = null, tail = null. Insert the value 7. What are head, tail, and node.next afterward?

Forecast: Guess before reading — where does the single new node's arrow point?

Detect the empty case. Test head == null. Why this step? The general insert code assumes a tail exists so it can do tail.next = x. With no tail, that line would crash. The empty list is a separate branch.
Create node x with value 7. x.next = x. Why this step? A CLL must have no dangling null. The only box available for x to loop to is itself, so the one-node loop is x → x. Look at the self-arrow in the figure.
Set head = x and tail = x. Why this step? With one node, "first" and "last" are the same box, so both labels point at x.

Verify: Traverse using "stop at start." Start at head, visit it, move p = p.next = x = start → stop. We visited exactly 1 node. Correct.

Example 2 — Single node stays a loop (Cell B)

Example 3 — Insert front and back, keep the loop (Cell C)

Worked example Two inserts on a growing CLL

Start with CLL A (single node, A → A, so tail = A). Do: (1) insert B at the front, (2) insert C at the back. Give the final cyclic order and tail.

Forecast: After both inserts, which node is tail, and what does tail.next equal?

Insert B at front. B.next = tail.next (which is head = A); then tail.next = B. Why this step? tail.next is the head, so we splice B in front of the head and re-close the loop through tail. Now order is B → A → B, head = B, tail still = A. What it looks like: the top row of the figure — new arrow into A, tail's arrow now hits B.
Insert C at back. Same splice: C.next = tail.next (= B, the head); tail.next = C; then tail = C. Why the extra line? Front and back inserts are identical except back-insert also moves the tail label to the new node. That single line is the whole difference.

Verify: Walk from head B: B → A → C → (C.next = B = start) stop. Cyclic order B, A, C, 3 nodes, tail = C, and tail.next = B = head. Loop intact. Correct.

Example 4 — Delete a middle node (Cell D)

Worked example Remove from the middle

CLL cyclic order 1 → 2 → 3 → 4 → (back to 1). Delete 3. We hold a pointer prev = 2.

Forecast: How many pointer writes does it take, and what's the new order?

Name the victim: victim = prev.next, so victim = 2.next = 3. Why this step? We only physically hold prev. The node we actually want to remove is the one right after it — we give it the name victim before we touch any arrows.
Relink: prev.next = victim.next, i.e. 2.next = 3.next = 4. Why this step? Node 3 is only reachable through 2's arrow. Redirect that one arrow past victim and nothing points to 3 anymore — it's gone. One write.
(Optional) free victim (node 3). Why this step? Its memory is now unreachable; reclaim it. The loop is unaffected because 4's arrow to 1 was never touched.

Verify: Walk from 1: 1 → 2 → 4 → 1 (start) stop. 3 nodes remain, order 1, 2, 4. Deletion cost = 1 pointer update = $O (1)$ . Correct.

Example 5 — Delete the head (Cell E)

Worked example Head deletion, tail must be told

CLL order 1 → 2 → 3 → (back to 1), tail = 3 (so tail.next = 1 = head). Delete the head 1.

Forecast: Which arrow must change besides the head label?

Name the victim: victim = head, so victim = 1. Why this step? Deleting the head means the head node is the victim; naming it keeps the next steps consistent with the general delete pattern.
New head is victim.next = 2. Why this step? The "first" label simply slides to the next box.
Re-close the loop: tail.next = new head = 2. Why this step? The tail was pointing at the old head 1 (the victim), which is being removed. If we forget this line, tail still points at the deleted node — a dangling arrow into freed memory. This is the whole reason head-deletion is a special case.

Verify: Walk from new head 2: 2 → 3 → (3.next = 2 = start) stop. 2 nodes, order 2, 3, and tail.next = 2 = head. Loop intact. Correct.

Example 6 — Delete the tail (Cell E)

Worked example Tail deletion, tail label must move back

CLL order 1 → 2 → 3 → (back to 1), tail = 3, and we hold prev = 2 (the node just before the tail). Delete the tail 3.

Forecast: After removing 3, which node becomes the new tail, and what must its next be?

Name the victim: victim = tail, so victim = 3. Why this step? The node we remove is the tail itself; giving it a name keeps us aligned with the general "relink past the victim" pattern.
Relink past the victim: prev.next = victim.next, i.e. 2.next = 3.next = 1 (head). Why this step? prev (node 2) was pointing at the victim. Redirect it to whatever the victim pointed to — the head — so the loop re-closes without 3.
Move the tail label back: tail = prev, so tail = 2. Why this step? The old tail is gone, so the new last node is prev. If we forget this, tail dangles at freed memory — the mirror-image bug of the head-deletion case. Now tail.next = 1 = head, exactly as the definition requires.

Verify: Walk from head 1: 1 → 2 → (2.next = 1 = start) stop. 2 nodes, order 1, 2, new tail = 2, and tail.next = 1 = head. Loop intact. Correct.

Example 7 — Traversal that must not run forever (Cell F)

Worked example Count the nodes of a CLL (and handle empty)

Two lists: (a) 10 → 20 → 30 → (back to 10); (b) the empty list (head = null). Count the nodes of each with one correct routine.

Forecast: If you jumped straight into a do-while on the empty list, what would break?

Pre-check the empty case: if head == null: return 0. Why this step? The next step reads p.next. On an empty list p = head = null, so p.next dereferences null and crashes. The do-while has no chance to stop it — we must bail out before the loop. For list (b) this returns 0 immediately.
Set start = head, p = head, count = 0. Why this step? We remember where we began so we can recognise the wrap. Only reached when at least one node exists.
Do-while: do { count++; p = p.next; } while (p != start); Why a do-while? If we used a plain while (p != start), the very first test head != head is false, so we'd count 0 and never enter — visiting nothing. The do-while forces the head to be counted once before checking.

Step	p before	count after	p after
1	10	1	20
2	20	2	30
3	30	3	10 = start → stop

Verify: List (a) → count = 3, matching three nodes. List (b) → the pre-check returns 0 with no dereference. A while (p != null) loop on (a) would never stop (no null exists) — the classic CLL infinite loop. Correct.

Example 8 — Josephus with wrap-around counting (Cell G)

Worked example Josephus, n = 7, k = 3

Seven people 1..7 in a circle. Starting the count at person 1, eliminate every 3rd person. Find the survivor.

Forecast: Guess the survivor number 1–7 before working it out.

Model the circle as a CLL 1 → 2 → … → 7 → 1. Why this step? Counting wraps past 7 back to 1 — exactly the CLL loop. No modular index arithmetic needed; the arrows do it.
Count 3, holding the node before the victim so deletion is prev.next = victim.next ( $O (1)$ ).

Kill #	count from	3rd person = victim	circle after
1	1	3	1 2 4 5 6 7
2	4	6	1 2 4 5 7
3	7 (wraps 7→1→2)	2	1 4 5 7
4	4	7	1 4 5
5	1 (wraps 1→4→5)	5	1 4
6	1 (wraps 1→4→1)	4	1

The figure below lays the seven people on a circle with the CLL arrows in lavender; each red #label marks the order in which that person is eliminated, and the lone mint node in the centre calls out the survivor. Trace the red numbers #1…#6 and you replay the table above visually.

Verify: Survivor = 4. We can double-check without redoing the whole simulation using a shortcut formula, explained next.

Derivation WHY the Josephus recurrence

$J (n) = (J (n - 1) + k) mod n$ works Number the people 0-indexed as $0, 1, \dots, n - 1$ and let $J (n)$ be the survivor's 0-indexed position when there are $n$ people and we eliminate every $k$ -th (counting starts at position 0).

Base case: with one person, that person survives, so $J (1) = 0$ . Why? Nobody else to eliminate.
The shrink step: the very first person eliminated sits at position $(k - 1) mod n$ . After removing them, $n - 1$ people remain, and — this is the key — counting restarts from the person right after the victim, at position $k mod n$ .
So the smaller problem $J (n - 1)$ is solved in a circle whose "position 0" is that restart point. To translate the smaller answer back to the original numbering, we shift every position forward by $k$ (the restart offset) and wrap with $mod n$ . That gives exactly $J (n) = (J (n - 1) + k) mod n$ . What it looks like: imagine peeling one seat off the circle and renumbering the survivors starting from the next live seat — the $+ k$ is that renumbering slide, and $mod n$ closes the loop. Finally add 1 to convert the 0-indexed answer to a person number. For $n = 7, k = 3$ this yields person 4, matching the table.

Example 9 — Ring buffer overflow (Cell H)

Worked example Ring buffer of size 4

A ring buffer (fixed circular array) of size 4 with write pointer w and read pointer r, both starting at slot 0. Do: write a, b, c, d, then write e, then read once. What value is returned, and what's in the buffer at the end?

Forecast: Does writing e succeed, and which old value dies?

Write a,b,c,d. After each write w = (w+1) mod 4. Now slots [a,b,c,d], w wrapped back to 0, r = 0. Buffer is full (w caught up to r). Why mod 4? Slot after the last (index 3) is the first (index 0) — the circular wrap.
Write e (overwrite mode). e lands in slot w = 0, overwriting a (the oldest). Then w = 1, and — because the buffer was already full — we also push r = 1 so it always points at the oldest surviving value. Why overwrite a? The loop makes "after the last slot comes the first," and slot 0 held the oldest datum. Streaming buffers keep the newest window, so the oldest (a) is sacrificed.

Look at the figure: the left ring shows the full buffer with w and r both parked on slot 0 (the red/mint dot stacked on a). The lavender arrow "write e" carries you to the right ring, where slot 0 now holds e (red = write pointer moved to slot 1) and r has been bumped to slot 1 (mint) — visually confirming that the oldest slot was consumed by the overwrite. Compare the two [i] slot labels across the rings and you can watch a disappear.

Read once. Returns slot r = 1, which is b; then advance r = (r+1) mod 4 = 2. Why this step? A read must return the oldest surviving value and then retire it, so the next read moves on. r points at exactly that oldest value; after handing back b, we advance r by one (mod 4) so a future read won't return b again. Since a was overwritten in step 2, b is now the oldest, which is why the read yields b.

Verify: Final buffer contents (slot order 0..3) [e, b, c, d]; the read returned b; r = 2 afterward. Data ages FIFO-style, newest 4 kept: b, c, d, e. This is exactly how audio/network streaming buffers behave — see Ring Buffer and Queue. Correct.

Example 10 — Round-robin real-world (Cell I)

Worked example CPU round-robin scheduling, quantum = 3

An operating system must fairly share the CPU among three processes: P(burst 5), Q(burst 2), R(burst 4) (burst = total CPU time each needs). The scheduler uses a CLL P → Q → R → P and a time quantum of 3 (max CPU each process gets before its turn passes). Compute the finish order and the total CPU time used.

Forecast: Which process finishes last?

Round 1 — run P for min(3, 5) = 3. Remaining P=2, Q=2, R=4. Move current = P.next = Q. Why min? A process can't use more than its remaining burst; the quantum is a cap, not a fixed amount.
Run Q for min(3, 2) = 2 → Q done, delete. Remaining P=2, R=4. Circle shrinks to P → R → P; current = R. Why delete? Once Q's burst hits 0 it never needs the CPU again, so we splice its node out (prev.next = Q.next) — the rotation now skips it automatically.
Run R for min(3, 4) = 3. Remaining P=2, R=1. current = R.next = P.
Run P for min(3, 2) = 2 → P done, delete. Remaining R=1. current = R.
Run R for min(3, 1) = 1 → R done. All finished.

Slice	ran	time	remaining after
1	P	3	P2 Q2 R4
2	Q	2	P2 R4 (Q done)
3	R	3	P2 R1
4	P	2	R1 (P done)
5	R	1	(R done)

Verify: Finish order Q, P, R. Total CPU time = $3 + 2 + 3 + 2 + 1 = 11 = 5 + 2 + 4$ (sum of bursts) — no time is invented or lost. Correct. See Round-Robin Scheduling.

Example 11 — Exam twists: k = 1, k > n (Cell J)

Worked example Two limiting Josephus cases

With $n = 5$ people: (a) $k = 1$ — who survives? (b) $k = 8$ — reduce the huge step and find the first person eliminated.

Forecast: For $k = 1$ , does the first or last person survive?

(a) k = 1: every count of 1 lands on the very next person, so we eliminate 1, 2, 3, 4 in order. Why? Step of 1 means "kill whoever you point at," marching forward. The last one left is 5. Survivor (a) = 5.
(b) k = 8, n = 5: counting 8 around a circle of 5 is the same as counting $8 mod 5 = 3$ (a full lap of 5 returns you to the start). Why mod? Every 5 steps you complete one loop back to where you were, so only the remainder matters. Starting the count at person 1, the 3rd person is 3 — the first eliminated.

Verify: (a) survivor = 5; (b) $8 mod 5 = 3$ , first eliminated = person 3. Both checked numerically below. Correct.

Recall Quick self-test across all cells

Empty-list insert makes the node point to ::: itself, and sets head = tail = node. Correct traversal stop condition ::: p == start with a do-while (never p == null). Traversal must first guard against ::: head == null (return 0) before the loop, else it dereferences null. Deleting the head requires also setting ::: tail.next = new head to re-close the loop. Deleting the tail requires also setting ::: tail = prev (move the tail label back one node). Josephus n=7, k=3 survivor ::: person 4. Ring buffer size 4, write a,b,c,d,e then read → returns ::: b (a was overwritten). Round-robin quantum 3 on P5 Q2 R4 finish order ::: Q, P, R. Josephus n=5, k=1 survivor ::: person 5.