FundamentalsData structureaka ring list, cyclic list, circular list

Circular Linked List

A linked list whose last node points back to the first, so traversal wraps around and a single tail pointer gives O(1) access to both ends.

▶ Visualize Pattern: Fast & Slow Pointers Practice (3)

Progress

Definition

In a circular linked list the final node's next refers to the head instead of null (a doubly linked variant also sets head.prev = tail). There is no natural end: starting from any node and following next eventually returns to the start.

The practical payoff is that keeping just a `tail` pointer gives O(1) access to both ends — the head is tail.next — so a queue needs only one pointer. The other payoff is fairness: round-robin schedulers, turn-based games, and the Josephus problem all naturally "go around the table".

Circular lists are less common in interviews as a required structure, but they explain why cycle detection matters: a list that accidentally becomes circular makes every naive while node != null loop run forever. Fast & Slow Pointers (Floyd) is the standard way to detect it.

ringwrap-aroundtail pointerround robinJosephusno null

Intuition

A mental model before the formal terms.

A group of people holding hands in a circle. Whoever you start from, walking to the left eventually brings you back. If you know the last person in "line", you also know the first — they are holding hands.

A clock face is a circular list of twelve numbers: after 12 comes 1. Modular arithmetic ((i + 1) % n) is the array analogue; a circular list gives the same wrap-around with O(1) insertion anywhere.

How it works

Keep a single tail pointer. Empty list: tail = null. One node: tail.next = tail.
pushBack(v): node.next = tail.next; tail.next = node; tail = node. Head stays tail.next.
pushFront(v): same as pushBack but do not advance tail — the new node becomes tail.next, i.e. the head.
popFront(): head = tail.next; tail.next = head.next (if head == tail, set tail = null).
rotate(): tail = tail.next — the old head becomes the new tail in O(1). This is round-robin.
Traversal: do { visit(cur); cur = cur.next } while (cur != tail.next) — a do/while because the stop condition is the start node, not null.
Cycle detection on an arbitrary list: slow moves 1, fast moves 2; if they meet the list is circular (or contains a cycle).

Why it works

Because tail.next is the head by construction, both ends are one pointer dereference away, which is why a queue needs only tail.

Traversal terminates because the list is a single cycle containing every node: starting at tail.next and stopping when we return to it visits each node exactly once.

Rotation is O(1) because the "end" is a matter of which node we call tail; the physical ring never changes.

Operations

Operation	Description	Cost
pushBack(v)	Link after `tail`, then advance `tail`.	O(1)
pushFront(v)	Link after `tail` without advancing `tail`.	O(1)
popFront()	Unlink `tail.next`.	O(1)
peekFront() / peekBack()	`tail.next.value` / `tail.value`.	O(1)
rotate()	Advance `tail` one step; old head becomes the tail.	O(1)
search(v)	Walk the ring once starting at the head.	O(n)
deleteAfter(node)	Skip `node.next`; adjust `tail` if it was removed.	O(1)
hasCycle(head)	Floyd slow/fast pointer check on an arbitrary list.	O(n)

Recognition

How to tell a problem wants this.

Round-robin scheduling, turn taking, "the next player after the last is the first".
The Josephus problem or "eliminate every k-th person in a circle".
Circular buffers/queues described in terms of wrap-around (compare Circular Queue on an array).
A linked-list problem that hints the list may contain a cycle — reach for Floyd's algorithm.

“cycle in linked list” → Fast & Slow Pointers “reverse a linked list” → Linked List Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Singly Linked List visualization.

Commands — Comma separated: append N, prepend N, insert N at I, delete N, reverse

empty list

1/30Start with an empty list: head = null. Each node stores a value and a single `next` pointer, so traversal is one-directional.

VisitingInsertedRemovedMatch

PseudocodeLearn Singly Linked List →

1append(v): walk to the tail; tail.next = Node(v)
2prepend(v): node = Node(v); node.next = head; head = node
3insert(v, i): walk to node i-1; node.next = prev.next; prev.next = node
4delete(v): walk until curr.value == v; prev.next = curr.next
5reverse(): prev = null; curr = head
6  while curr: next = curr.next; curr.next = prev; prev = curr; curr = next
7  head = prev

Variables

size0

Complexity

access O(n)

search O(n)

insert O(1)

delete O(1)

Speed

Pseudocode

1class Node: value, next
2class CircularLinkedList: tail = null, size = 0
3pushBack(v): n = Node(v)
4  if tail == null: n.next = n; tail = n
5  else: n.next = tail.next; tail.next = n; tail = n
6  size++
7pushFront(v): pushBack(v) but do not move tail (tail stays the old tail)
8popFront(): head = tail.next
9  if head == tail: tail = null else tail.next = head.next
10  size--; return head.value
11rotate(): if tail: tail = tail.next
12traverse(): if tail == null return; cur = tail.next
13  do: visit(cur); cur = cur.next while cur != tail.next

Implementation

1from typing import Generic, Iterator, Optional, TypeVar
2 
3T = TypeVar("T")
4 
5 
61 · Node and tail-only handle
7class RingNode(Generic[T]):
8    __slots__ = ("value", "next")
9 
10    def __init__(self, value: T, next: "Optional[RingNode[T]]" = None) -> None:
11        self.value = value
12        self.next = next
13 
14 
15class CircularLinkedList(Generic[T]):
16    def __init__(self) -> None:
17        self.tail: Optional[RingNode[T]] = None  # tail.next is the head
18        self._n = 0
19 
20    def __len__(self) -> int:
21        return self._n
22 
23    def is_empty(self) -> bool:
24        return self.tail is None
25 
262 · Push back (link into the ring, advance tail)
27    def push_back(self, v: T) -> None:
28        if self.tail is None:
29            node: RingNode[T] = RingNode(v)
30            node.next = node
31            self.tail = node
32        else:
33            node = RingNode(v, self.tail.next)
34            self.tail.next = node
35            self.tail = node
36        self._n += 1
37 
383 · Push front (same link, tail stays)
39    def push_front(self, v: T) -> None:
40        if self.tail is None:
41            self.push_back(v)
42            return
43        self.tail.next = RingNode(v, self.tail.next)
44        self._n += 1
45 
464 · Pop front
47    def pop_front(self) -> T:
48        if self.tail is None:
49            raise IndexError("pop from empty ring")
50        head = self.tail.next
51        assert head is not None
52        if head is self.tail:
53            self.tail = None
54        else:
55            self.tail.next = head.next
56        self._n -= 1
57        return head.value
58 
595 · Rotate (O(1): head becomes tail)
60    def rotate(self) -> None:
61        if self.tail is not None:
62            self.tail = self.tail.next
63 
646 · Traverse once around the ring
65    def __iter__(self) -> Iterator[T]:
66        if self.tail is None:
67            return
68        head = self.tail.next
69        cur = head
70        while True:
71            assert cur is not None
72            yield cur.value
73            cur = cur.next
74            if cur is head:
75                break

Walkthrough

Only tail is stored; tail.next is the head.
push_back self-links on an empty ring, otherwise splices after tail and advances it.
push_front splices in the same position but leaves tail unchanged.
pop_front removes the head; a one-node ring collapses to None.
rotate is one assignment; __iter__ is a generator that yields once around the ring with an explicit break when it returns to head.

Complexity (this implementation)

time O(1) push_back/push_front/pop_front/rotate, O(n) traverse · space O(n)

A ring holds a reference cycle, so nodes are freed by the cycle collector, not immediately by refcounting.

Language notes

collections.deque.rotate(k) gives O(k) rotation on a ready-made structure; for round-robin over a fixed set it beats a hand-rolled ring.
itertools.cycle(iterable) yields elements forever — the functional take on a ring.
Defining __iter__ as a generator makes for v in ring and list(ring) work.

Common mistakes in this language

while cur is not None traversal never ends on a ring.
print(ring) or repr on nodes that reference each other can recurse without a custom __repr__.
Forgetting the single-node case in pop_front.

Language differences that matter here

Iteration protocol: JS/TS [Symbol.iterator] and Python __iter__ make the ring usable in for loops; C++ would need a custom iterator type or the visitor callback shown.
Memory: C++ must pop every node explicitly (following next never reaches null); JS collects cycles; Python needs the cycle collector because refcounts never hit zero.
Built-in alternatives: Python deque.rotate and itertools.cycle; nothing equivalent in C++ or JS beyond modular indexing over an array.
Serialisation: JSON.stringify (JS) and default repr (Python) choke on the cycle; C++ has no default printing to worry about.

Complexity

Operation	Average	Worst	Note
Access	O(n)	O(n)	O(1) for head (`tail.next`) and tail.
Search	O(n)	O(n)
Insert	O(1)	O(1)	At either end or after a known node.
Delete	O(1)	O(1)	Front, or after a known node; O(n) to delete the tail in a singly circular list.
Update	O(n)	O(n)	O(1) once located.
Rotate	O(1)	O(1)
Cycle detection	O(n)	O(n)	Floyd, O(1) space.
Space	O(n)		Only one list-level pointer (`tail`) is needed for queue behaviour.

Advantages & disadvantages

Advantages

O(1) access to both ends with a single tail pointer — a compact queue.
O(1) rotation makes round-robin iteration trivial.
Traversal can begin at any node and still cover the whole list.
No null at the end; every node always has a valid successor.

Disadvantages

Infinite loops if the termination condition is written as != null.
Requires a do/while or explicit start-node check for traversal; harder to reason about than a terminated list.
Same O(n) access and search as any linked list; no cache locality.
Singly circular lists still need the predecessor for deletion; doubly circular lists cost two pointers per node.

Use cases

Round-robin CPU/process schedulers and load balancers cycling through workers.
Multiplayer turn order; music playlists on repeat.
Josephus problem and similar elimination games.
Fibonacci heap root lists and other structures that splice rings in O(1).
Simple queues with one pointer in memory-constrained embedded code.

Use it when

Round-robin iteration over a set that changes over time (schedulers, turn order).
A queue where you want O(1) enqueue/dequeue with a single pointer.
Elimination games (Josephus) where the "next" after the last is the first.

Avoid it when

Ordinary sequential processing — a terminated Singly Linked List is simpler and safer.
Fixed-capacity ring buffers — a Circular Queue on an array is faster and cache-friendly.
Any situation where accidental infinite loops would be costly and the wrap-around is not needed.

Alternatives

Circular Queue Singly Linked List Doubly Linked List Deque

Common mistakes

Writing while (cur != null) — the loop never ends; use a do/while that stops at the start node.
Forgetting the single-node case where tail.next == tail, so popping must set tail = null.
Advancing tail on pushFront (turns it into pushBack) or not advancing it on pushBack.
Deleting the tail node without updating tail, leaving a dangling reference into freed memory.
Building a ring by mistake in a normal list (e.g. reorder/rotate problems) and not terminating with null.

Interview patterns

Josephus problem: simulate with a ring in O(n·k), or derive the O(n) recurrence J(n) = (J(n-1) + k) mod n.
Rotate a list right by k: connect tail to head, then break the ring at n - k mod n.
Detect a cycle and find its entry point with Floyd's algorithm.
Insert into a sorted circular list given any node (handle wrap-around and all-equal cases).
Split a circular list into two halves using slow/fast pointers.

Interview questions on this

Array versus linked listBeginner

Interview problems

Linked List Cycleeasy Middle of the Linked Listeasy Find the Duplicate Numbermedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related