PK

PKBytes

Explore tracks
Chapter 11: Linked Lists
11.04Beginner / Intermediate5 topics14 min2 interactive animations

Circular linked lists

Circular linked lists connect the last node back to the first, so there is no null end. This lesson covers singly and doubly circular lists, safe loop termination, a circular queue and the Josephus problem.

Learning goals

  • Build and traverse a circular list without looping forever
  • Implement a queue with one tail pointer
  • Solve Josephus by unlinking nodes

Prerequisites

Singly linked operationsDoubly linked lists
11.04.1

Singly circular

In a circular singly linked list the last node's next points to the first node instead of null. Keeping a reference to the tail (rather than the head) gives O(1) access to both ends: tail.next is the head. It suits round-robin scheduling and any structure that cycles.

The last arrow in the Josephus animation returns to the first node.

Java
1class CircularList {
2    Node tail;                                   // tail.next is the head
3    void addLast(int v) {
4        Node n = new Node(v);
5        if (tail == null) { n.next = n; }
6        else { n.next = tail.next; tail.next = n; }
7        tail = n;
8    }
9    void addFirst(int v) {
10        Node n = new Node(v);
11        if (tail == null) { n.next = n; tail = n; }
12        else { n.next = tail.next; tail.next = n; }      // tail stays the same
13    }
14}

Josephus problem on a circular linked list

Interactive · edit the input

Your input

Try

linked list · 7 nodes

1
2
3
4
5
6
7
null
cur
prev
Person being countedEliminatedSurvivor

elimination order

none yet
Setup

7 people stand in a circle (the last arrow points back to the first). Count 3, remove that person, and continue counting from the next one.

Step 1 / 20
Java
1static int josephus(int n, int k) {                  // people 1..n stand in a circle
2    Node first = buildCircle(n);                     // circular list: last.next = first
3    Node prev = lastNode(first), cur = first;
4    for (int left = n; left > 1; left--) {
5        for (int i = 1; i < k; i++) { prev = cur; cur = cur.next; }   // count k people
6        prev.next = cur.next;                        // unlink the k-th person
7        cur = cur.next;                              // counting restarts after the removed person
8    }
9    return cur.val;                                  // the only node left
10}

Live state

n

7

k

3

No condition evaluated on this step
Execution trace (dry run table)Show 20 steps
StepLineStateWhat happens
1L2n=7 k=37 people stand in a circle (the last arrow points back to the first). Count 3, remove that person, and continue counting from the next one.
2L5left=7 count=2 cur=2Count 2: person 2.
3L5left=7 count=3 cur=3Count 3: person 3.
4L6left=6 removed=3Person 3 is the 3-th: prev.next = cur.next unlinks them. 6 remain.
5L5left=6 count=2 cur=5Count 2: person 5.
6L5left=6 count=3 cur=6Count 3: person 6.
7L6left=5 removed=6Person 6 is the 3-th: prev.next = cur.next unlinks them. 5 remain.
8L5left=5 count=2 cur=1Count 2: person 1.
9L5left=5 count=3 cur=2Count 3: person 2.
10L6left=4 removed=2Person 2 is the 3-th: prev.next = cur.next unlinks them. 4 remain.
11L5left=4 count=2 cur=5Count 2: person 5.
12L5left=4 count=3 cur=7Count 3: person 7.
13L6left=3 removed=7Person 7 is the 3-th: prev.next = cur.next unlinks them. 3 remain.
14L5left=3 count=2 cur=4Count 2: person 4.
15L5left=3 count=3 cur=5Count 3: person 5.
16L6left=2 removed=5Person 5 is the 3-th: prev.next = cur.next unlinks them. 2 remain.
17L5left=2 count=2 cur=4Count 2: person 4.
18L5left=2 count=3 cur=1Count 3: person 1.
19L6left=1 removed=1Person 1 is the 3-th: prev.next = cur.next unlinks them. 1 remain.
20L9return=4Person 4 survives. Simulating with a circular list costs O(n·k); the recurrence J(n) = (J(n - 1) + k) mod n finds it in O(n).
11.04.2

Doubly circular

A doubly circular list also links the first node's prev to the last node. With a sentinel node whose next and prev both point to itself when the ring is empty, no operation ever needs a null check. Rotating the ring is just moving one pointer.

Use it when you need to walk in either direction around a ring.

Java
1class Ring {
2    final DNode sentinel = new DNode(0);
3    Ring() { sentinel.next = sentinel; sentinel.prev = sentinel; }      // empty ring
4    void addLast(int v) {
5        DNode n = new DNode(v), last = sentinel.prev;
6        n.prev = last; n.next = sentinel;
7        last.next = n; sentinel.prev = n;
8    }
9}
11.04.3

Loop termination

A loop over a circular list must not wait for null, because it never comes. Stop when you return to the starting node: use a do-while (visit first, then test), or count the nodes. Take care with the empty list, where there is no start node, and with removal during traversal, which can remove the start node itself.

The same idea detects that you have gone around once.

Java
1static int sum(Node tail) {                    // tail.next is the head; null means empty
2    if (tail == null) return 0;
3    int total = 0;
4    Node cur = tail.next;                      // head
5    do {
6        total += cur.val;
7        cur = cur.next;
8    } while (cur != tail.next);                // stop when we are back at the head
9    return total;
10}
11.04.4

Circular queue implementation

A queue can be a circular singly linked list with one tail reference: enqueue inserts after the tail (the new node becomes the tail), and dequeue removes tail.next, the head. Both are O(1) and only one reference is stored. When the last node is removed the queue becomes empty (tail = null). An array-based circular buffer is the usual alternative.

Chapter 13 builds the array version.

Java
1class LinkedQueue {
2    private Node tail;                           // null when empty
3    void enqueue(int v) {
4        Node n = new Node(v);
5        if (tail == null) n.next = n; else { n.next = tail.next; tail.next = n; }
6        tail = n;
7    }
8    int dequeue() {
9        if (tail == null) throw new NoSuchElementException();
10        Node head = tail.next;
11        if (head == tail) tail = null; else tail.next = head.next;
12        return head.val;
13    }
14}
11.04.5

Josephus problem

In the Josephus problem n people stand in a circle and every k-th person is eliminated until one is left. With a circular list you count k nodes, unlink the k-th by relinking its predecessor, and continue from the next node: O(n·k) time. The recurrence J(1) = 0, J(n) = (J(n - 1) + k) mod n (zero-based) gives the survivor in O(n) without simulation.

Try n = 7, k = 3 and read the elimination order.

Java
1static int josephusList(int n, int k) {                  // survivor, 1-based
2    Node first = new Node(1), cur = first;
3    for (int i = 2; i <= n; i++) { cur.next = new Node(i); cur = cur.next; }
4    cur.next = first;                                      // close the circle
5    Node prev = cur; cur = first;
6    for (int left = n; left > 1; left--) {
7        for (int i = 1; i < k; i++) { prev = cur; cur = cur.next; }
8        prev.next = cur.next;                              // unlink the k-th person
9        cur = cur.next;
10    }
11    return cur.val;
12}
13static int josephusMath(int n, int k) { int r = 0; for (int i = 2; i <= n; i++) r = (r + k) % i; return r + 1; }

Josephus problem on a circular linked list

Interactive · edit the input

Your input

Try

linked list · 7 nodes

1
2
3
4
5
6
7
null
cur
prev
Person being countedEliminatedSurvivor

elimination order

none yet
Setup

7 people stand in a circle (the last arrow points back to the first). Count 3, remove that person, and continue counting from the next one.

Step 1 / 20
Java
1static int josephus(int n, int k) {                  // people 1..n stand in a circle
2    Node first = buildCircle(n);                     // circular list: last.next = first
3    Node prev = lastNode(first), cur = first;
4    for (int left = n; left > 1; left--) {
5        for (int i = 1; i < k; i++) { prev = cur; cur = cur.next; }   // count k people
6        prev.next = cur.next;                        // unlink the k-th person
7        cur = cur.next;                              // counting restarts after the removed person
8    }
9    return cur.val;                                  // the only node left
10}

Live state

n

7

k

3

No condition evaluated on this step
Execution trace (dry run table)Show 20 steps
StepLineStateWhat happens
1L2n=7 k=37 people stand in a circle (the last arrow points back to the first). Count 3, remove that person, and continue counting from the next one.
2L5left=7 count=2 cur=2Count 2: person 2.
3L5left=7 count=3 cur=3Count 3: person 3.
4L6left=6 removed=3Person 3 is the 3-th: prev.next = cur.next unlinks them. 6 remain.
5L5left=6 count=2 cur=5Count 2: person 5.
6L5left=6 count=3 cur=6Count 3: person 6.
7L6left=5 removed=6Person 6 is the 3-th: prev.next = cur.next unlinks them. 5 remain.
8L5left=5 count=2 cur=1Count 2: person 1.
9L5left=5 count=3 cur=2Count 3: person 2.
10L6left=4 removed=2Person 2 is the 3-th: prev.next = cur.next unlinks them. 4 remain.
11L5left=4 count=2 cur=5Count 2: person 5.
12L5left=4 count=3 cur=7Count 3: person 7.
13L6left=3 removed=7Person 7 is the 3-th: prev.next = cur.next unlinks them. 3 remain.
14L5left=3 count=2 cur=4Count 2: person 4.
15L5left=3 count=3 cur=5Count 3: person 5.
16L6left=2 removed=5Person 5 is the 3-th: prev.next = cur.next unlinks them. 2 remain.
17L5left=2 count=2 cur=4Count 2: person 4.
18L5left=2 count=3 cur=1Count 3: person 1.
19L6left=1 removed=1Person 1 is the 3-th: prev.next = cur.next unlinks them. 1 remain.
20L9return=4Person 4 survives. Simulating with a circular list costs O(n·k); the recurrence J(n) = (J(n - 1) + k) mod n finds it in O(n).

Practice ladder

Now try it yourself

Easy

  • How do you detect that you have gone around a circular list once?
  • What does an empty circular list with a tail reference look like?

Medium

  • Find the survivor for n = 5, k = 2 by hand
  • Implement dequeue for the circular linked queue

Advanced

  • Prove the Josephus recurrence J(n) = (J(n - 1) + k) mod n

Key takeaways

  • A tail reference gives O(1) access to both ends of a circular list.
  • Never loop until null; stop when you return to the start.
  • Josephus: unlink every k-th node, or use the O(n) recurrence.