Circular Linked Lists

A circular linked list is an ordinary singly linked list with one knot tied: instead of the last node's next pointing at null, it points back at the first. Follow next long enough and you arrive where you started. To keep that cheap, the list stores a tail pointer alongside head, and the single invariant it guards is tail.next == head.

That one change rewrites how you stop. A normal list traversal ends when it hits null; a ring never hits null, so a loop written that way spins forever. The replacement is to stop when you come back to the head — curr == head. Hold onto that and the whole structure follows; forget it and your first search for a missing value hangs the program.

How a Circular Linked List Works

Picture a relay baton passed around a circle of runners. Each runner knows only the next runner; the last hands back to the first. There is no "finish line" built into the track — if you want the lap to end, you have to notice you've returned to the runner you started with and call it.

Every operation keeps the loop closed. insert_head and insert_tail are both O(1) because the list holds both ends: a head insert points the new node at the old head and re-aims tail.next at it; a tail insert points the new node at the head, links the old tail to it and advances tail. No walk to the end: that is the stored tail at work, and a singly list that keeps a tail appends in O(1) too. Either way the last act is re-establishing tail.next = head, the beat the animation draws as the wrap arrow swinging to its new target.

search is where the ring shows its teeth. The walk starts at head and follows next. On a match it stops mid-ring and returns the index. On no match it advances off the tail, rides the wrap back to the head, and the guard curr == head fires — that is the stop, not a null check. A successful and a failed search end two different ways, and the failed one is the lesson: the walk physically completes a lap and halts at the start.

delete finds the node by walking (O(n), same lap-aware loop), then rewires its predecessor past it. The ring makes the end cases interesting: deleting the head re-aims tail.next at the new head; deleting the tail moves tail back to the predecessor; deleting the only node dissolves the ring to empty.

One honest disclosure: the capacity slider (4–10 nodes, default 7) exists only because the canvas fits so many boxes. The code mirrors it with a max field, but a real linked list has no capacity.

Circular Linked List Operations Step by Step

The ring starts empty. Run this sequence from the Inputs panel:

1. Insert Head 5 — the first node. With nothing else around, it points at itself: 5.next = 5, a single-node self-loop, and head and tail both land on it. Ring: 5 ↺.
2. Insert Head 8 — node 8 points at the old head: 8.next = 5. Then the wrap re-aims: tail (5).next = 8, and head swings to 8. Ring: 8 → 5 → (back to 8).
3. Insert Tail 3 — no walk; the tail pointer is already at 5. Node 3 points at the head: 3.next = 8 (the new wrap). Then 5.next = 3 and tail advances to 3. Ring: 8 → 5 → 3 → (back to 8).
4. Insert Tail 7 — again O(1). 7.next = 8, 3.next = 7, tail advances to 7. Ring: 8 → 5 → 3 → 7 → (back to 8).
5. Search 3 — walk from the head: index 0 is 8 ≠ 3, index 1 is 5 ≠ 3, index 2 is 3 = 3. Found at index 2, and the walk stops mid-ring.
6. Search 9 — the one to watch. Walk the whole ring: 8 ≠ 9, 5 ≠ 9, 3 ≠ 9, 7 ≠ 9. The cursor advances off the tail, rides the wrap arrow back, and lands on the head. The guard curr == head fires: stop, not found. No null was ever involved.

On the canvas, the forward next links ride the row and the wrap link arcs through a band below it, from the tail's pointer back to the head — always on screen, so "this is a ring" never needs explaining. On the failed search, the cursor travels that arc itself, so you see the walk come home rather than teleport.

Time and Space Complexity

Against a singly list the storage is identical — still one pointer per node. O(1) tail insertion comes from the kept tail, which a singly list can hold as well. What the ring itself buys is a structure with no special "end," which is why it backs round-robin schedulers and circular buffers. What it costs is the discipline of a different stop condition.

Edge Cases

• The single-node ring — one node whose next points at itself (node.next = node). head and tail are the same node. The animation draws this as a small self-loop, not a wrap to a different box.
• Delete the head — the new head is the old head's successor, and tail.next must follow it so the ring stays closed: head = node.next, then tail.next = head.
• Delete the tail — tail moves back to the predecessor, and that node becomes the new wrap origin: tail = prev, tail.next = head.
• Delete the only node — both pointers go null and the ring dissolves to empty.
• Search or delete a missing value — the walk completes exactly one lap and stops at the head (curr == head), returning -1 / False. It never loops forever and never touches null.
• Search on an empty ring — the if not self.head guard returns immediately, before any walk.

Common Mistakes

• Stopping at null. The reflex while curr: or while curr.next: never terminates on a ring — curr is never null. The correct loop advances first and then checks curr == head. This is the single most common circular-list bug, and the default search 9 exists to make it concrete.
• Letting the wrap go stale. Every insert and every end-node delete has to re-establish tail.next = head. Append a node but forget to repoint the old tail and the ring silently breaks into a line with a dangling link — or worse, a loop that skips the newest node.
• Forgetting the tail pointer on a tail delete. Removing the last node without moving tail back leaves tail pointing at freed-from-the-ring memory, and the next insert appends to a node that's no longer there.
• Mishandling the single node. Deleting the only node (head == tail) must null both pointers, and inserting into an empty ring must self-loop the new node. Extending a one-node ring is the ordinary case: the new node points at the head, not at itself. Code that assumes at least two nodes corrupts these cases.