The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Circular Lists

Next ►
►

Every list we have built so far ends the same way: a last node whose next is None, the "it ends here" signal that stops our traversals. In this lesson we remove that signal on purpose: the last node will point to the first, closing the chain into a ring. The result is the circular list, in its singly and doubly linked variants, a structure tailor-made for problems that never end: turns that rotate, fair distributions, processes that start over. In TaskFlow we will give it its natural use: the cyclic distribution of tasks among team members, round-robin style. But a ring without None is also a trap: any traversal written "the usual way" (while current is not None) becomes an infinite loop. Learning to traverse with the right stopping condition is as important here as the structure itself.

Contents

  1. Closing the ring: what changes and what breaks
  2. Singly linked circular list: implementation with insertion and removal
  3. Safe traversals: correct stopping conditions
  4. Round-robin: cyclic distribution in TaskFlow
  5. Doubly linked circular list: the ring with a reverse gear
  6. When (and when not) to use a circular list

Closing the ring: what changes and what breaks

The structural change is a single arrow: where the singly linked list had last.next = None, the circular one has last.next = first.

graph LR
    A["Anna"] --> B["Bruno"]
    B --> C["Carla"]
    C -- "the arrow that closes the ring" --> A
    U[last] --> C

Immediate consequences:

  • None no longer exists as an end signal. Every traversal must invent another stopping condition; otherwise, it will spin forever. It is danger number one and we devote an entire section to it.
  • The distinction "being at the front / being at the back" disappears in the physical sense: from any node you can reach any other simply by advancing. The ring has no ends, only whatever reference point we decide on.
  • A single reference is enough to manage it: by keeping self.last, the first is always self.last.next. Two for the price of one — that is how we get O(1) insertion at both "ends" without maintaining two references.

Singly linked circular list: implementation with insertion and removal

We reuse the Node class from 02-02 (data + next); what changes is the container:

class CircularList:
    """Singly linked circular list: the last node points to the first."""
    def __init__(self):
        self.last = None    # reference to the last; the first is last.next
        self.size = 0

    def is_empty(self):
        return self.last is None

    def insert_back(self, data):
        """Adds after the last and becomes the new last. Cost: O(1)."""
        new_node = Node(data)
        if self.is_empty():
            new_node.next = new_node         # it points to itself!
            self.last = new_node
        else:
            new_node.next = self.last.next   # 1: the new node looks at the first
            self.last.next = new_node        # 2: the old last hooks it on
            self.last = new_node             # 3: the last moves
        self.size += 1

    def __len__(self):
        return self.size

Pause at the empty-list case: the first node points to itself (new_node.next = new_node). It is the minimal ring, of a single link, and it satisfies the definition: the last (itself) points to the first (itself). Many bugs in circular lists are born from mishandling this case.

And insert_front? Here circularity hands us a gem: in a ring, inserting at the front and inserting at the back are exactly the same rewiring — the new node always hooks in between the last and the first. The only difference is whether self.last moves to the new node (then the new node is the last: insertion at the back) or stays where it was (then the new node, being "the last one's next", is the new first: insertion at the front):

    def insert_front(self, data):
        """Adds ahead of the first. Cost: O(1)."""
        new_node = Node(data)
        if self.is_empty():
            new_node.next = new_node
            self.last = new_node
        else:
            new_node.next = self.last.next
            self.last.next = new_node
            # self.last is untouched: the new node ends up as the first
        self.size += 1

And the removal, with its double edge case:

    def remove(self, condition):
        """Removes the first node (in traversal order) meeting the condition.
        Returns the data or None. Cost: O(n)."""
        if self.is_empty():
            return None
        prev = self.last
        current = self.last.next              # we start at the first
        for _ in range(self.size):            # at most, one full lap
            if condition(current.data):
                if current is current.next:           # only node in the ring
                    self.last = None
                else:
                    prev.next = current.next          # bridge
                    if current is self.last:          # we removed the last
                        self.last = prev
                self.size -= 1
                return current.data
            prev = current
            current = current.next
        return None
  • The prev/current pattern from 02-02 is still in force, with an extra elegance: prev starts at self.last, which is exactly the node before the first. In a circular list, every node has a predecessor; there is no special head case.
  • The "only node" case is detected with current is current.next (it points to itself) and empties the list.
  • The loop's stopping condition is no longer None: it is counting (for _ in range(self.size)), the first of the safe traversal techniques we formalize next.

Safe traversals: correct stopping conditions

The lethal mistake in circular lists is this:

# NEVER with a circular list!
current = ring.last.next
while current is not None:      # it will never be None: infinite loop
    print(current.data)
    current = current.next

There are two correct techniques, each with its own terrain:

Technique 1 — Counting the nodes (requires a reliable size):

    def __iter__(self):
        """One full lap starting at the first. Cost: O(n)."""
        if self.is_empty():
            return
        current = self.last.next
        for _ in range(self.size):
            yield current.data
            current = current.next

Technique 2 — The sentinel node: remember the starting node and stop upon seeing it again:

def one_lap(ring):
    """Walks the ring exactly once, without using size."""
    if ring.is_empty():
        return
    start = ring.last.next
    current = start
    while True:
        print(current.data)
        current = current.next
        if current is start:      # we are back at the starting point: done
            break
Technique Requires Advantage Risk
Counting (range(size)) A correct counter Simple, no identity comparisons If size is wrong, one lap too many or too few
Sentinel (is start) Nothing extra Works even without a counter Check after advancing; with == instead of is, false stops

Two sentinel details worth an exam question: the comparison uses is (identity: the same node, not equal data — two distinct tasks could hold equal data) and it happens after advancing, not before; if you check at the top of the loop, the condition is true on the first iteration and nothing gets visited. The while True + break-after-advancing pattern solves that "do at least one pass" cleanly.

Round-robin: cyclic distribution in TaskFlow

The TaskFlow team has a classic problem: distributing incoming tasks in a fair, rotating fashion among its members — each new task goes to the next member in the rotation, and after the last one, back to the first. This scheme is called round-robin and it is everywhere: operating systems sharing CPU among processes, load balancers sharing requests among servers, games sharing turns among players. Its natural structure is the ring:

class TaskDispatcher:
    """Assigns tasks to team members in a rotating turn."""
    def __init__(self, names):
        self.team = CircularList()
        for name in names:
            self.team.insert_back(name)
        self.turn = self.team.last    # the "turn pointer" on the ring

    def assign(self, task):
        """Assigns the task to the next member in the rotation. Cost: O(1)."""
        self.turn = self.turn.next              # advance the turn (there is never an end)
        task["assigned_to"] = self.turn.data
        return task

    def remove_member(self, name):
        """A member leaves the team: out of the ring. Cost: O(n)."""
        if self.turn.data == name:               # don't leave the turn on the one leaving
            self.turn = self.turn.next
        self.team.remove(lambda d: d == name)


dispatcher = TaskDispatcher(["Anna", "Bruno", "Carla"])

tasks = [{"id": i, "title": f"Task {i}", "priority": 2, "status": "pending"}
         for i in range(1, 8)]
for t in tasks:
    dispatcher.assign(t)
    print(f'{t["title"]} -> {t["assigned_to"]}')

Output:

Task 1 -> Anna
Task 2 -> Bruno
Task 3 -> Carla
Task 4 -> Anna        ← the ring starts over, without a single if
Task 5 -> Bruno
Task 6 -> Carla
Task 7 -> Anna

The elegance is in assign: there is no "have I reached the end?" check whatsoever. With a regular list we would have written the classic index = (index + 1) % len(team), with its modular arithmetic; the ring wraps around by pure topology: advancing always works. On top of that, team joins and departures (people entering and leaving the rotation) are the cheap insertions and removals linked lists give us without shifting anyone — with the fine detail in remove_member: if the turn sat on whoever is leaving, it advances before removing them, so we don't end up pointing at a node outside the ring.

Doubly linked circular list: the ring with a reverse gear

If we close the ring over double nodes (DoubleNode from 02-03), we get the doubly linked circular list: last.next is the first and first.prev is the last. All arrows matched, no None anywhere in the structure.

graph LR
    A["Anna"] -- next --> B["Bruno"]
    B -- prev --> A
    B -- next --> C["Carla"]
    C -- prev --> B
    C -- next --> A
    A -- prev --> C
class DoublyCircularList:
    """Doubly linked ring: navigable in both directions, with no ends."""
    def __init__(self):
        self.ref = None       # some node of the ring ("the first")
        self.size = 0

    def insert(self, data):
        """Inserts before the reference (= at the back of the ring). Cost: O(1)."""
        new_node = DoubleNode(data)
        if self.ref is None:
            new_node.next = new_node     # a one-link ring...
            new_node.prev = new_node     # ...in both directions
            self.ref = new_node
        else:
            last = self.ref.prev                   # the last one comes free!
            new_node.prev = last                   # the new node looks both ways
            new_node.next = self.ref
            last.next = new_node                   # the neighbors return the gaze
            self.ref.prev = new_node
        self.size += 1

    def remove_node(self, node):
        """Takes the node out of the ring. Cost: O(1) given the node."""
        if node.next is node:                # only link
            self.ref = None
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
            if node is self.ref:
                self.ref = node.next
        self.size -= 1
        return node.data

Two gifts from double circularity:

  • The last one comes free: self.ref.prev. In the singly linked circular list, reaching the node before a given one cost a full lap; here it is one arrow. That is why this class doesn't need to store last: with a single reference it has both "ends" one hop away.
  • remove_node with no head or tail cases: in a double ring, all nodes are interior — node.prev and node.next always exist. Compare with the four branches of the linear doubly linked list from 02-03: here only the "single link" case remains, plus the care not to leave ref on the departing node. Circularity, which looked like a complication, simplifies removal.

Why would TaskFlow want the double version? For a rotating turn that can also be undone: "task 7 got canceled, give the turn back to whoever had it before" is self.turn = self.turn.prev, O(1). With the singly linked circular list, stepping the turn back would cost a full lap around the ring.

When (and when not) to use a circular list

Situation Circular? Why
Rotating turns (round-robin, games, load balancing) Yes The "after the last, the first" is the structure, not an if
Looping playback (playlist, carousel, cyclic animation) Yes The traversal must never end
A buffer that overwrites itself circularly Yes (a kindred idea) Module 4's circular queue uses this same idea on an array
A sequence with a clear start and end (the task board) No The final None is information: "there is no more"; the ring destroys it
You need traversals that stop on their own No Every stop demands a counter or a sentinel: gratuitous complexity

The practical rule: use a circular list when rotation is part of the problem domain, not as a general substitute for the linear list. The TaskFlow board will remain linear; the turn rotation, circular. Each structure in its place.

Common Mistakes and Tips

  • The infinite loop from while current is not None. The defining mistake of circular lists. The moment a list is circular, that pattern is forbidden: either you count nodes or you use a sentinel. If your program "hangs" while traversing, it is almost certainly this.
  • Checking the sentinel before advancing. while current is not start as the loop's first line doesn't run a single iteration (you start at start). The correct pattern visits, advances, and then compares.
  • Using == instead of is with the sentinel. Two distinct nodes may hold equal data (two tasks with the same title); == would stop at the impostor. Node identity is always checked with is.
  • Forgetting the one-link ring. The node that points to itself (in the double version, in both directions) is the edge case of every circular list: inserting the first and removing the last must create and undo it carefully. Test your methods with lists of 0, 1, and 2 nodes, as always.
  • Leaving an external reference on a removed node. The dispatcher's self.turn or the double ring's self.ref must move before removing the node they point at. A turn pointer on a node outside the ring will hand tasks to a ghost.
  • Tip: with circular lists, paper diagrams matter even more than with linear ones: draw the ring, mark the external reference, and simulate removing the pointed-at node. The three previous mistakes are visible at a glance in the drawing.

Exercises

Exercise 1 — A homegrown Josephus. The TaskFlow team draws lots for who presents the demo: standing in a circle, they count off by 3 and whoever is pointed at is eliminated; the last one standing wins. Write survivor(names, k) that, using CircularList (or circular nodes by hand), eliminates every k-th person and returns the name of the last one. Test with ["Anna", "Bruno", "Carla", "David", "Elena"] and k=3. (This is the Josephus problem, a classic with two thousand years of history.)

Exercise 2 — A turn with a reverse gear. Extend TaskDispatcher so it uses DoublyCircularList and add the method undo_assignment(), which steps the turn back one position in O(1) (the next task will again go to whoever was due before the last assignment). Demonstrate with a sequence: assign 4 tasks, undo one, assign another.

Exercise 3 — Counted laps. Write a function traverse_laps(ring, n_laps) that walks the ring exactly n_laps full times using the sentinel technique (without using size), returning the list of visited data. Verify with a 3-element ring and 2 laps that it returns 6 items and that each lap starts at the same node.

Solutions

Solution 1:

def survivor(names, k):
    """Josephus problem on a ring. Cost: O(n·k)."""
    ring = CircularList()
    for name in names:
        ring.insert_back(name)

    prev = ring.last
    current = ring.last.next            # the first
    while len(ring) > 1:
        for _ in range(k - 1):          # advance k-1 places
            prev = current
            current = current.next
        print("Eliminated:", current.data)
        prev.next = current.next              # bridge: out of the ring
        if current is ring.last:
            ring.last = prev
        ring.size -= 1
        current = prev.next             # the one after the eliminated keeps counting
    return ring.last.data

print(survivor(["Anna", "Bruno", "Carla", "David", "Elena"], 3))

Output: Carla is eliminated, then Anna, then Elena, then Bruno — David survives. Notice that the elimination uses the usual bridge (prev.next = current.next) and that the ring makes "keep counting from the next one" natural: there is no special case when passing where the eliminated one used to be. With a list you would need index juggling with %; with the ring, topology does the work for us.

Solution 2:

class TaskDispatcherV2:
    def __init__(self, names):
        self.team = DoublyCircularList()
        for name in names:
            self.team.insert(name)
        self.turn = self.team.ref.prev   # so the 1st assigned is the 1st inserted

    def assign(self, task):
        self.turn = self.turn.next             # advance: O(1)
        task["assigned_to"] = self.turn.data
        return task

    def undo_assignment(self):
        """Returns the turn to its previous position. Cost: O(1)."""
        self.turn = self.turn.prev             # the 'prev' arrow in action!


dispatcher = TaskDispatcherV2(["Anna", "Bruno", "Carla"])
for i in range(1, 5):
    t = dispatcher.assign({"id": i, "title": f"T{i}", "priority": 2, "status": "pending"})
    print(t["title"], "->", t["assigned_to"])   # Anna, Bruno, Carla, Anna
dispatcher.undo_assignment()                     # the turn steps back to Carla
t = dispatcher.assign({"id": 5, "title": "T5", "priority": 2, "status": "pending"})
print(t["title"], "->", t["assigned_to"])        # T5 -> Anna (it's their turn again)

undo_assignment is a single assignment thanks to the double ring's prev arrow: exactly the operation that in the singly linked circular list would have cost a full lap. It is the same moral as 02-03 (the extra arrow buys O(1) steps backward), now in ring form.

Solution 3:

def traverse_laps(ring, n_laps):
    """Walks the ring n_laps times with a sentinel. Without using size."""
    if ring.is_empty() or n_laps <= 0:
        return []
    start = ring.last.next        # sentinel: the first
    visited = []
    laps = 0
    current = start
    while True:
        visited.append(current.data)
        current = current.next
        if current is start:          # compare AFTER advancing, with 'is'
            laps += 1
            if laps == n_laps:
                break
    return visited

ring = CircularList()
for x in ("A", "B", "C"):
    ring.insert_back(x)
print(traverse_laps(ring, 2))   # ['A', 'B', 'C', 'A', 'B', 'C']

Six items, and each lap starts at the same node A: the sentinel works. The three ingredients of the safe traversal are in plain sight: sentinel fixed before starting, comparison with is, and the check after advancing. Change any of the three and you will get, depending on the case, zero iterations, false stops, or an eternal loop.

Conclusion

Closing the ring — making the last node point to the first, and in the double version the other way around too — turns the list into the natural structure for everything that rotates: TaskFlow's round-robin dispatcher assigns turns without modular arithmetic or end checks, the Josephus problem is solved with the usual bridge, and the double ring gifts us O(1) turn rollback and a removal with no head or tail cases. In exchange, we lost the None that stopped traversals, and we learned the two disciplines that replace it: counting nodes or watching a sentinel with is after advancing. With this, the list family is complete: singly linked, doubly linked, and circular, each with its cost table and its place in TaskFlow. In the next lesson there will be no new theory: it will be pure training — reversing lists, detecting cycles with two pointers, merging boards sorted by priority, moving tasks between positions, and finishing off the navigable history — the exercises that turn what you've learned into craft, several of them absolute classics of the technical interview.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved