Circular Linked List

A Circular Linked List is a variation of a linked list where the last node points back to the first node instead of containing a null reference. This creates a circular structure that can be traversed indefinitely.

Circular linked lists can be either singly linked (each node has one pointer) or doubly linked (each node has two pointers). The circular nature enables continuous traversal and is particularly useful in round-robin scheduling and buffer implementations.

The main advantage of circular linked lists is that any node can be a starting point, and the entire list can be traversed from any node. This makes them ideal for applications that require cyclic processing.

Key Property: The last node's next pointer always points back to the first node, creating a continuous loop.

Basic Operations

Operation	Complexity	Description
Insertion at Head	O(1)	Add new node at beginning, point last node to new head
Insertion at Tail	O(1)	Add new node at end, point it to head (with tail pointer)
Deletion at Head	O(1)	Remove first node, update last node's pointer
Deletion by Value	O(n)	Traverse list to find and remove specific node
Traversal	O(n)	Loop through nodes until returning to starting point
Search	O(n)	Traverse list to find element

Insertion Process

1. Create new node with data
2. If list is empty, set head and tail to new node
3. Make new node point to itself (circular reference)
4. For non-empty list, set new node's next to current head
5. Update tail's next pointer to new node
6. Move head pointer to new node

head

[A]

[B]

Existing circular list

↓ Insert X at head ↓

head

[X]

[A]

[B]

Deletion Process

1. Check if list is empty
2. If single node exists, set head and tail to null
3. For head deletion, update head to head.next
4. Update tail's next pointer to new head
5. For middle deletion, find node and update previous node's pointer
6. Handle special case when deleting last node

head

[X]

[A]

[B]

Current circular list

↓ Delete X (head) ↓

head

[A]

[B]

Operation Visualization

Operation	List State
Initialization	head → null
insertFirst(10)	head → [10] → (points back to head)
insertFirst(20)	head → [20] → [10] → (points back to head)
insertFirst(30)	head → [30] → [20] → [10] → (points back to head)
deleteFirst()	head → [20] → [10] → (points back to head)
delete(10)	head → [20] → (points back to itself)

Comparison with Linear Linked List

Feature	Linear Linked List	Circular Linked List
Structure	Linear with null termination	Circular with no null
Traversal	Stops at end	Continuous loop
Memory Overhead	Standard	Same as linear
Boundary Detection	Easy (null check)	Requires start reference
Insert/Delete at Head	O(1)	O(1)
Implementation Complexity	Simpler	More complex

Pros and Cons

Advantages

Continuous traversal from any node
Efficient round-robin scheduling
No need for null checks during traversal
Useful for circular buffer implementations

Limitations

Risk of infinite loops if not handled carefully
Slightly more complex implementation
Harder to detect list boundaries

Applications

Operating system round-robin scheduling
Multiplayer turn-based games
Music/video playlists with repeat functionality
Resource allocation in networking
Circular buffer implementations
Token ring networks

When to Choose: Prefer circular linked lists when you need continuous cycling through elements or when the application naturally follows a circular pattern (like round-robin scheduling).

Visualize Circular Linked List Operations

Node Value

Empty List

Add nodes to visualize the circular linked list

Test Your Knowledge before moving forward!

Linked List Quiz Challenge

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Circular Linked List Implementation

// Circular Linked List Implementation in JavaScript
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // Insert at beginning
  insertFirst(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = this.head; // Point to itself
    } else {
      newNode.next = this.head;
      this.head = newNode;
      this.tail.next = this.head; // Update tail's next to new head
    }
    this.size++;
  }

  // Insert at end
  insertLast(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = this.head;
    } else {
      this.tail.next = newNode;
      newNode.next = this.head;
      this.tail = newNode;
    }
    this.size++;
  }

  // Insert at index
  insertAt(data, index) {
    if (index < 0 || index > this.size) return;
    if (index === 0) return this.insertFirst(data);
    if (index === this.size) return this.insertLast(data);

    const newNode = new Node(data);
    let current = this.head;
    let count = 0;

    while (count < index - 1) {
      current = current.next;
      count++;
    }

    newNode.next = current.next;
    current.next = newNode;
    this.size++;
  }

  // Remove from beginning
  removeFirst() {
    if (!this.head) return null;
    const removedNode = this.head;
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.tail.next = this.head; // Update tail's next to new head
    }
    this.size--;
    return removedNode.data;
  }

  // Remove from end
  removeLast() {
    if (!this.head) return null;
    const removedNode = this.tail;
    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      let current = this.head;
      while (current.next !== this.tail) {
        current = current.next;
      }
      current.next = this.head; // Point new tail to head
      this.tail = current;
    }
    this.size--;
    return removedNode.data;
  }

  // Remove at index
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    if (index === 0) return this.removeFirst();
    if (index === this.size - 1) return this.removeLast();

    let current = this.head;
    let count = 0;
    while (count < index - 1) {
      current = current.next;
      count++;
    }
    const removedNode = current.next;
    current.next = removedNode.next;
    this.size--;
    return removedNode.data;
  }

  // Get at index
  getAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current = this.head;
    let count = 0;
    while (count < index) {
      current = current.next;
      count++;
    }
    return current.data;
  }

  // Clear list
  clear() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // Print list
  print() {
    if (!this.head) {
      console.log("List is empty");
      return;
    }
    let current = this.head;
    let result = "";
    do {
      result += current.data + " -> ";
      current = current.next;
    } while (current !== this.head);
    result += "(head)";
    console.log(result);
  }

  // Check if list is circular
  isCircular() {
    if (!this.head) return true;
    let slow = this.head;
    let fast = this.head.next;
    while (fast && fast.next) {
      if (slow === fast) return true;
      slow = slow.next;
      fast = fast.next.next;
    }
    return false;
  }
}

// Usage Example
const cll = new CircularLinkedList();
cll.insertFirst(100);
cll.insertFirst(200);
cll.insertLast(300);
cll.insertAt(500, 1);
cll.print(); // 200 -> 500 -> 100 -> 300 -> (head)
cll.removeAt(2);
console.log(cll.getAt(1)); // 500
console.log("Is circular:", cll.isCircular()); // true

Explore Other Types

Singly Linked List

Doubly Linked List