Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 225 ยท Linked Lists

Circular Linked Lists

Learn circular linked lists in Python: the tail-pointer trick, safe traversal, circular doubly lists, round-robin scheduling and the Josephus problem.

An ordinary linked list ends with None: the last node points at nothing. In a circular linked list the last node points back to the first, so the chain forms a ring. There is no natural end. If you keep following next, you go around forever.

That sounds like a bug, but a ring is exactly the right shape for anything that repeats: players taking turns, a scheduler giving each task a time slice, a music playlist on repeat. In this lesson you will build circular lists, learn how to traverse them without looping forever, and solve the classic Josephus problem with a ring, with a plain list, and with a formula.

The picture

TEXT
Singly linked:     head -> [A] -> [B] -> [C] -> None

Circular:                  +-----------------+
                           v                 |
                  tail -> [C] -> [A] -> [B] -+
                           (tail.next is the head)

In the circular version we keep a reference to the tail instead of the head. The head is always tail.next, so one pointer gives us both ends. That small choice is the core trick of this lesson.

The tail-pointer trick

With a normal singly linked list and only a head pointer, adding at the back costs O(n) because you must walk to the end. With a circular list that stores tail:

  • Add at the front: new.next = tail.next; tail.next = new (the tail does not change). O(1).
  • Add at the back: do the same thing, then move tail = new. O(1).
  • Remove the front: tail.next = tail.next.next. O(1).

Both ends are cheap, with just one pointer and a single link per node.

Python A circular list with a tail pointer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at append. It calls prepend and then advances tail. Because a ring has no real "front" or "back" except where we say the break is, inserting right after the tail and then declaring the new node the tail is exactly the same wiring.

A single node in a circular list points to itself (node.next is node). That is what keeps the ring valid for size 1, and it removes the empty-list special case from rotate and traversal.

Traversing safely

The classic mistake is a loop written for linear lists:

Python
node = head
while node is not None:    # never true in a ring: infinite loop
    node = node.next

There are two safe patterns.

Count the nodes. If you track size, loop exactly size times, as __iter__ above does.

Stop when you return to the start. This needs a loop that runs the body first and tests afterward (a do-while). Python has no do-while, so use while True with a break:

Python Traverse until you return to the start

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Starting at any node visits the whole ring once, only shifted. This also shows a useful fact: in a circular list every node is equally a "head".

Watch out: when you delete from a ring, check the one-node case. If the node you remove points to itself, the list becomes empty and tail must be set to None. Forgetting this leaves a dangling ring that is never freed and never empty.

Use case 1: round-robin scheduling

An operating system shares one CPU among many tasks by giving each a short time slice in turn. When a task's slice ends and work remains, it goes to the back of the line. That is a rotation on a ring:

Python Round-robin scheduler

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trace it with a quantum of 2: A runs 2 (3 left), B runs 2 (done and removed), C runs 2 (2 left), A runs 2 (1 left), C runs 2 (done), A runs 1 (done). The ring shrinks as jobs finish, and the loop never needs to know where the "end" is.

Use case 2: the Josephus problem

Problem. n people stand in a circle, numbered 1 to n. Starting at person 1, count k people and eliminate the one you land on; counting resumes from the next person. Continue until one person remains. Who survives?

TEXT
n = 7, k = 3:     1 2 3 4 5 6 7
count 1-2-3 -> out 3     (resume at 4)
count 4-5-6 -> out 6     (resume at 7)
count 7-1-2 -> out 2     (resume at 4)
count 4-5-7 -> out 7     (resume at 1)
count 1-4-5 -> out 5     (resume at 1)
count 1-4-1 -> out 1     (resume at 4)
survivor: 4

Solution 1: simulate with a circular linked list

Walk k - 1 steps, then unlink the next node. Each elimination costs O(k) steps, so the total is O(nยทk) time and O(n) space.

Solution 2: simulate with a Python list

Keep the people in a list and a running index. After each removal the next count starts at the same index, wrapped with %. Removing from the middle of a list shifts items, costing O(n) per removal, so this is O(nยฒ) time. For small n it is the shortest code.

Solution 3: the recurrence

Let J(n) be the survivor's position when positions are numbered from 0. With one person, the survivor is position 0. With n people, the first elimination removes position (k-1) % n; the remaining n-1 people form a smaller circle that starts counting right after the removed person. A position p in that smaller circle corresponds to position (p + k) % n in the big one. So:

TEXT
J(1) = 0
J(n) = (J(n-1) + k) % n        (add 1 at the end for 1-based numbering)

That is a single loop: O(n) time and O(1) space.

Python Josephus three ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The formula handles a hundred thousand people instantly, while the ring simulation would do hundreds of thousands of pointer steps. When a problem has this kind of structure, a recurrence beats simulation. Compare the shape of this idea with the recurrences lesson.

Circular doubly linked lists

You can close the ring in a doubly linked list too: the last node's next points to the first and the first node's prev points to the last. A neat version uses one sentinel node that is part of the ring:

TEXT
 +-------> [S] <------------------+
 |  next    ^ |  prev             |
 |          | v                   |
 |         [A] <-> [B] <-> [C] ---+
 +------------------------------->
 S.next = A, S.prev = C, C.next = S, A.prev = S

An empty list is just S.next = S.prev = S. Insert and delete use the same two-neighbor routines as before, with no special case anywhere. Several LRU cache designs use exactly this layout.

Python One-sentinel circular doubly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Operation Circular singly (tail pointer) Circular doubly (sentinel)
Access front O(1) O(1)
Access back O(1) O(1)
Insert at front/back O(1) O(1)
Remove front O(1) O(1)
Remove back O(n), need predecessor O(1)
Rotate by one O(1) O(1)
Search O(n) O(n)
Space O(n) O(n)

Common mistakes

  • Infinite loops. A while node is not None loop never ends on a ring. Count nodes or compare against the starting node.
  • Forgetting to close the ring when building, so traversal crashes with AttributeError on None.
  • Forgetting the one-node and empty cases when deleting. A one-node ring is node.next is node.
  • Updating tail at the wrong time in append: wire the node in first, then move the tail.
  • Printing a node's repr in a ring: default object printing is fine, but any recursive __repr__ that follows next will recurse until Python's recursion limit.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do circular lists usually store a tail pointer instead of a head pointer?

    The last node points to the first, so from the tail you reach the head in one step and can also append in O(1).
  2. 2. What goes wrong with this loop on a circular list: while node is not None: node = node.next?

    In a ring every node has a successor, so the condition stays true forever. Count nodes or stop when you return to the start.
  3. 3. In the Josephus problem with n = 7 and k = 3, who is eliminated first and who survives?

    Counting 1, 2, 3 removes person 3 first. The full elimination order is 3, 6, 2, 7, 5, 1, leaving 4.
  4. 4. What is the time complexity of the formula J(n) = (J(n-1) + k) % n computed with a loop?

    The loop runs once per size from 2 to n with constant work in each iteration and keeps only one number.
  5. 5. In a circular singly linked list with only a tail pointer, which operation is NOT O(1)?

    Removing the tail requires its predecessor, and a singly linked ring has no prev pointer, so you must walk around the ring: O(n).

Summary

  • A circular linked list closes the chain so the last node points to the first; a lone node points to itself.
  • Keeping a tail pointer gives O(1) access to both ends, because the head is tail.next.
  • Traverse by counting nodes or by stopping when you return to the starting node; never test for None.
  • Rings model repeating processes: round-robin scheduling, turn order, playlists on repeat.
  • The Josephus problem can be simulated with a ring (O(nยทk)), with a list (O(nยฒ)), or solved with the recurrence J(n) = (J(n-1) + k) % n in O(n) time and O(1) space.
  • A circular doubly linked list with one sentinel node needs no special cases and removes any node in O(1).

Next: Linked List Techniques