DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Basics

Intermediate

Circular Linked List

The tail node's next pointer loops back to HEAD — no NULL terminator. Perfect for round-robin schedulers and circular buffers.

No NULL Terminator

Interactive Operations

Circular Invariant

Circular Linked List

Every node has a next pointer. The tail wraps back to HEAD — no NULL at the end.

Color Legend

DefaultTraversingTarget foundCompleteCircular link

Speed:

List is empty — insert to begin

Size

–

HEAD

–

TAIL

Insert, delete, search, or traverse to see the circular connection in action.

Complexity

O(1)

Insert Head / Tail

O(n)

Insert at Index

O(1)

Delete Head

O(n)

Search / Delete Mid

O(n) Space

n nodes, each with value + one next pointer

Key Properties

No NULL

tail.next = head — the list is a closed ring, no terminator

Traversal guard

Stop when current == head (not when next == NULL)

HEAD + TAIL

Two pointers give O(1) insert at both ends

Natural cycling

After the last node, iteration continues from the start

Real-World Uses

Round-robin CPU scheduling

Cycle through processes in order, wrapping around indefinitely

Circular buffer / ring buffer

Fixed-size FIFO where writer and reader chase each other

Multiplayer game turns

After the last player, the first player gets their turn again

Media playlists on loop

After the last track, the playlist restarts from the first

Test Yourself

Q1/3

In a circular linked list, how do you detect that a traversal has visited all nodes?

Python Implementation

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def insert_head(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.next = node             # self-loop
            self.head = self.tail = node
        else:
            node.next = self.head
            self.tail.next = node        # tail still points to new head
            self.head = node
        self.size += 1

    def insert_tail(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.next = node
            self.head = self.tail = node
        else:
            node.next = self.head        # new tail wraps to head
            self.tail.next = node
            self.tail = node
        self.size += 1

    def delete_head(self):               # O(1)
        if not self.head:
            raise IndexError("Empty list")
        val = self.head.value
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.head = self.head.next
            self.tail.next = self.head   # tail now points to new head
        self.size -= 1
        return val

    def traverse(self):                  # O(n) — stop at head
        if not self.head:
            return
        cur = self.head
        while True:
            yield cur.value
            cur = cur.next
            if cur == self.head:
                break

    def search(self, value):             # O(n)
        if not self.head:
            return -1
        cur, idx = self.head, 0
        while True:
            if cur.value == value:
                return idx
            cur, idx = cur.next, idx + 1
            if cur == self.head:
                return -1

DSAverse

Basics & Data Structures

Loading Data Structures...

Array Access

array[0..5]indexed access

Array

Stack

Queue

Back to Basics

Intermediate

Circular Linked List

The tail node's next pointer loops back to HEAD — no NULL terminator. Perfect for round-robin schedulers and circular buffers.

No NULL Terminator

Interactive Operations

Circular Invariant

Circular Linked List

Every node has a next pointer. The tail wraps back to HEAD — no NULL at the end.

Color Legend

DefaultTraversingTarget foundCompleteCircular link

Speed:

List is empty — insert to begin

Size

–

HEAD

–

TAIL

Insert, delete, search, or traverse to see the circular connection in action.

Complexity

O(1)

Insert Head / Tail

O(n)

Insert at Index

O(1)

Delete Head

O(n)

Search / Delete Mid

O(n) Space

n nodes, each with value + one next pointer

Key Properties

No NULL

tail.next = head — the list is a closed ring, no terminator

Traversal guard

Stop when current == head (not when next == NULL)

HEAD + TAIL

Two pointers give O(1) insert at both ends

Natural cycling

After the last node, iteration continues from the start

Real-World Uses

Round-robin CPU scheduling

Cycle through processes in order, wrapping around indefinitely

Circular buffer / ring buffer

Fixed-size FIFO where writer and reader chase each other

Multiplayer game turns

After the last player, the first player gets their turn again

Media playlists on loop

After the last track, the playlist restarts from the first

Test Yourself

Q1/3

In a circular linked list, how do you detect that a traversal has visited all nodes?

Python Implementation

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def insert_head(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.next = node             # self-loop
            self.head = self.tail = node
        else:
            node.next = self.head
            self.tail.next = node        # tail still points to new head
            self.head = node
        self.size += 1

    def insert_tail(self, value):        # O(1)
        node = Node(value)
        if not self.head:
            node.next = node
            self.head = self.tail = node
        else:
            node.next = self.head        # new tail wraps to head
            self.tail.next = node
            self.tail = node
        self.size += 1

    def delete_head(self):               # O(1)
        if not self.head:
            raise IndexError("Empty list")
        val = self.head.value
        if self.head == self.tail:
            self.head = self.tail = None
        else:
            self.head = self.head.next
            self.tail.next = self.head   # tail now points to new head
        self.size -= 1
        return val

    def traverse(self):                  # O(n) — stop at head
        if not self.head:
            return
        cur = self.head
        while True:
            yield cur.value
            cur = cur.next
            if cur == self.head:
                break

    def search(self, value):             # O(n)
        if not self.head:
            return -1
        cur, idx = self.head, 0
        while True:
            if cur.value == value:
                return idx
            cur, idx = cur.next, idx + 1
            if cur == self.head:
                return -1