DSA — Linear DS

Circular Linked List

Tail's next points back to head. No null terminator. Useful for round-robin scheduling.

— min read
O(n)Access
O(1)Insert
O(n)Search
○Circular
✓No NULL
// CIRCULAR LINKED LIST
Use buttons to operate on the list
How It Works
Python Code
Complexity
Quiz
Practice
01
Circular
tail.next = head, not null.
while cur.next != head: cur = cur.next
02
Traversal
Must check if back at head to stop.
cur != head
03
Append
Update tail.next = head after insert.
04
Uses
Round-robin scheduling, circular buffer, Josephus problem.
Python — CLL Append 
def append(self, val):
    node = Node(val)
    if not self.head:
        self.head = node
        node.next = self.head   # self-loop
        return
    cur = self.head
    while cur.next != self.head: cur = cur.next
    cur.next = node
    node.next = self.head       # circular!
O(1)
Insert Front
Update tail.next → new head
O(n)
Insert Tail
Traverse to find tail
↺
Always Connected
No null — circular
Careful
Infinite loop without stop condition
How do you know you completed a full traversal of a CLL?
Progress0 / 5 solved
5 problems · 3 PBC · 2 Startup
#2001 Linked List Cycle II Amazon, Google PBC →
#2002 Circular Array Loop Microsoft PBC →
#2003 Find the Duplicate Number Meta, Amazon PBC →
#2004 Josephus Problem Flipkart STARTUP →
#2005 Split Circular LL into Two Halves Zomato STARTUP →
← Doubly Linked List