Circular linked lists: keep one tail and a valid cycle

Operational case

Append D-19, D-47, and D-61. The first snapshot begins at D-19. Rotating once advances the tail reference from D-61 to D-19, which makes D-47 the new head without changing any node links. Removing that head returns D-47; the remaining ring reads D-61 followed by D-19. This convention implements fair turn order only if callers rotate or remove at the intended scheduling boundary. A ring by itself has no thread safety, job acknowledgment, or protection against a caller holding an old node reference.

Working Python program

"""Single-tail circular list for a small round-robin dispatch ring."""


class DispatchNode:
    def __init__(self, depot_id):
        self.depot_id = depot_id
        self.next = None


class DispatchRing:
    def __init__(self):
        self.tail = None
        self.length = 0

    def append(self, depot_id):
        node = DispatchNode(depot_id)
        if self.tail is None:
            node.next = node
        else:
            node.next = self.tail.next
            self.tail.next = node
        self.tail = node
        self.length += 1

    def rotate_once(self):
        if self.tail is not None:
            self.tail = self.tail.next

    def remove_front(self):
        if self.tail is None:
            raise IndexError("empty dispatch ring")
        front = self.tail.next
        if front is self.tail:
            self.tail = None
        else:
            self.tail.next = front.next
        self.length -= 1
        front.next = None
        return front.depot_id

    def snapshot(self):
        if self.tail is None:
            return []
        result = []
        current = self.tail.next
        for _ in range(self.length):
            result.append(current.depot_id)
            current = current.next
        return result


dispatch = DispatchRing()
for depot in ("D-19", "D-47", "D-61"):
    dispatch.append(depot)
print(dispatch.snapshot())
dispatch.rotate_once()
print(dispatch.remove_front())
print(dispatch.snapshot())

Output

['D-19', 'D-47', 'D-61']
D-47
['D-61', 'D-19']

Time, space, and tradeoff

Append, one-step rotation, and head removal each take O(1) time and use O(1) extra space. Capturing all N members takes O(N) time and O(N) output space. A rotation by K positions would take O(K mod N) link steps in this representation; it is not a constant-time arbitrary jump. Every member adds one node and one next link, so the ring uses O(N) space. Python's cyclic garbage collector can reclaim an unreachable ring, but a live reference to any node still keeps reachable nodes alive. Use a built-in deque when the application only needs ordinary end operations and no explicit node ownership.

Common Mistakes

• Do not leave a singleton pointing to None; it must point to itself.
• Do not use a null-terminated traversal condition on a cycle.
• Do not forget to repair tail.next when removing the head.
• Do not claim constant-time rotation by an arbitrary number of positions from this code.

Connected lessons

• Linked Lists
• Data Structures
• Singly linked lists: preserve head and tail invariants
• Doubly linked lists: relink known nodes safely
• Queues: preserve arrival order without front shifts
• Projects
• Quizzes

Use this invariant in the dispatch audit project, then check the operations quiz.