Circular Linked List

In a circular linked list, the last node does not point to null. Its next pointer points back to head, so the shape is 1 -> 2 -> 3 -> 1. The same idea can be applied to singly linked lists or doubly linked lists, where the tail and head are connected in both directions.

This changes the meaning of the boundary. There is no natural null at the end of a non-empty ring. A pointer can keep moving forever unless the algorithm remembers where it started or how many nodes it has processed.

The key rule is stop when you return to head, not when you see null. A common traversal starts at head, processes the current node, moves to current.next, and continues while current != head. Empty-list handling still checks whether head is null before entering the ring.

This termination rule is also the source of many bugs. If the loop condition checks current != null, the loop never ends. If it checks current != head before processing the first node, it may skip the entire list. Decide whether your loop is do-first or check-first and keep it consistent.

Circular lists model repeated turns. Round-robin scheduling can keep a pointer to the current process and advance to the next process after each time slice. Ring buffers use a circular idea over array indices, wrapping the write or read position back to the beginning when capacity is reached.

They also appear in Josephus-style problems: people stand in a circle, every k-th person is removed, and counting continues from the next person. Even if you solve Josephus with math or arrays, the circular-list framing explains why the pointer never falls off an end.

Many circular-list implementations keep a tail pointer instead of only head. When tail.next is head, appending after tail is local: set the new node's next to head, set tail.next to the new node, then move tail to the new node.

With only head, finding the tail still requires a full loop. As with ordinary linked lists, the asymptotic win depends on which pointer the algorithm already maintains.