Circular Linked List

A circular linked list is a linked list where the last node's next pointer points back to the first node (for singly circular) or where both head's prev and tail's next connect to each other (for doubly circular).

There is no null at the end — the list forms a closed loop. This makes it ideal for applications that need continuous cycling through elements.

Singly vs Doubly Circular

Property	Singly Circular	Doubly Circular
Last.next	Points to head	Points to head
Head.prev	Does not exist	Points to tail
Traversal	Forward only	Forward and backward
Insert at tail	O(n) if only head known	O(1) if tail known
Delete head	O(n) (need to update tail.next)	O(1)
Memory per node	One pointer	Two pointers

Node Structure

// Singly Circular Linked List Node
class SinglyNode {
  constructor(val) {
    this.val = val;
    this.next = this;  // initially points to itself (single node = circular)
  }
}

// Doubly Circular Linked List Node
class DoublyNode {
  constructor(val) {
    this.val = val;
    this.next = this;
    this.prev = this;
  }
}

// Creating a 3-node singly circular list: 1 → 2 → 3 → 1
const a = new SinglyNode(1);
const b = new SinglyNode(2);
const c = new SinglyNode(3);
a.next = b;
b.next = c;
c.next = a;  // close the circle

// Verify: starting at a, we should visit 1, 2, 3, then return to 1
let cur = a;
const visited = [];
do {
  visited.push(cur.val);
  cur = cur.next;
} while (cur !== a);
console.log(visited); // [1, 2, 3]

Traversal Without Infinite Loop

The critical rule for traversing a circular list: do not check for null. Instead, stop when you return to the starting node.

Use a do-while loop to ensure you process the head before checking the stop condition.

// Safe traversal of a circular linked list
function traverse(head) {
  if (!head) return [];
  const result = [];

  let cur = head;
  do {
    result.push(cur.val);
    cur = cur.next;
  } while (cur !== head);  // stop when we've looped back

  return result;
}

// Print n items (useful when you want to cycle multiple times)
function traverseN(head, n) {
  if (!head) return [];
  const result = [];
  let cur = head;
  let count = 0;

  while (count < n) {
    result.push(cur.val);
    cur = cur.next;
    count++;
  }

  return result;
}

// With the 3-node list above:
console.log(traverse(a));        // [1, 2, 3]
console.log(traverseN(a, 7));    // [1, 2, 3, 1, 2, 3, 1] — cycles!

Warning

Never use a `while (cur !== null)` loop on a circular linked list — it will run forever. Always check `cur !== head` (or track visited nodes with a counter/set).

Insertion

Inserting a node requires maintaining the circular property. If you maintain a tail pointer (or use the last node before head), insertion at both ends is straightforward.

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

  // Insert at the end — O(1) with tail pointer
  append(val) {
    const node = new SinglyNode(val);

    if (!this.head) {
      this.head = node;
      this.tail = node;
      node.next = node;  // circle of one
    } else {
      node.next = this.head;   // new node points to head
      this.tail.next = node;   // old tail points to new node
      this.tail = node;        // update tail
    }

    this.size++;
  }

  // Insert at the front — O(1) with tail pointer
  prepend(val) {
    const node = new SinglyNode(val);

    if (!this.head) {
      this.head = node;
      this.tail = node;
      node.next = node;
    } else {
      node.next = this.head;
      this.tail.next = node;  // tail still wraps around to new head
      this.head = node;
    }

    this.size++;
  }

  // Insert after a given node — O(1)
  insertAfter(targetVal, newVal) {
    if (!this.head) return;

    let cur = this.head;
    do {
      if (cur.val === targetVal) {
        const node = new SinglyNode(newVal);
        node.next = cur.next;
        cur.next = node;
        if (cur === this.tail) this.tail = node;  // update tail if needed
        this.size++;
        return;
      }
      cur = cur.next;
    } while (cur !== this.head);
  }

  toArray() { return traverse(this.head); }
}

const cll = new CircularLinkedList();
cll.append(1); cll.append(2); cll.append(3);
console.log(cll.toArray()); // [1, 2, 3]
cll.prepend(0);
console.log(cll.toArray()); // [0, 1, 2, 3]
cll.insertAfter(2, 2.5);
console.log(cll.toArray()); // [0, 1, 2, 2.5, 3]

Deletion

Deletion requires updating the circular link. The tricky case is deleting the head or tail — the tail's next must be updated to point to the new head.

// Delete a node by value — O(n)
deleteNode(val) {
  if (!this.head) return;

  // Special case: only one node
  if (this.head === this.tail && this.head.val === val) {
    this.head = null;
    this.tail = null;
    this.size--;
    return;
  }

  // Delete head
  if (this.head.val === val) {
    this.head = this.head.next;
    this.tail.next = this.head;  // update circular link
    this.size--;
    return;
  }

  // Find node before the one to delete
  let prev = this.head;
  let cur = this.head.next;

  do {
    if (cur.val === val) {
      prev.next = cur.next;
      if (cur === this.tail) this.tail = prev;  // update tail
      this.size--;
      return;
    }
    prev = cur;
    cur = cur.next;
  } while (cur !== this.head);
}

Use Cases for Circular Linked Lists

Round-robin CPU scheduling — processes cycle in a circle; when one finishes its time slice, the next one starts
Multiplayer board games — players take turns in a loop; no special end-of-list handling needed
Circular buffers / ring buffers — fixed-size data queues in OS kernels and audio processing
Music playlist on repeat — natural circular traversal
Token ring networking protocol — tokens pass around a ring of nodes
Josephus problem — circular elimination requires a circular structure

Josephus Problem

n people stand in a circle. Every k-th person is eliminated until one remains. Find the position of the last survivor (0-indexed).

The circular linked list models this directly — traverse and delete every k-th node. The mathematical solution is O(n) without any list at all.

// Josephus — Circular LL simulation O(n·k)
function josephusSimulation(n, k) {
  // Build circular list of n people (0-indexed)
  const head = new SinglyNode(0);
  let cur = head;
  for (let i = 1; i < n; i++) {
    cur.next = new SinglyNode(i);
    cur = cur.next;
  }
  cur.next = head;  // close the circle

  let prev = cur;   // prev = node before head (= last node)
  cur = head;

  while (cur.next !== cur) {
    // Advance k-1 steps (we're already on the 1st person)
    for (let i = 1; i < k; i++) {
      prev = cur;
      cur = cur.next;
    }
    // Eliminate cur
    prev.next = cur.next;
    cur = cur.next;  // continue from next person
  }

  return cur.val;
}

// Josephus — Mathematical O(n) solution (DP)
// josephus(n, k) = (josephus(n-1, k) + k) % n
// josephus(1, k) = 0
function josephusMath(n, k) {
  let pos = 0;
  for (let i = 2; i <= n; i++) {
    pos = (pos + k) % i;
  }
  return pos;
}

console.log(josephusSimulation(7, 3)); // 3
console.log(josephusMath(7, 3));       // 3

Tip

The mathematical Josephus solution is a beautiful DP recurrence. `josephus(n, k)` gives the 0-indexed survivor position. The circular linked list simulation is correct but slower — use it to understand the problem structure, use the math formula in practice.

Floyd's Cycle Detection Connection

Floyd's algorithm (fast/slow pointers) detects cycles in linked lists. A circular linked list always has a cycle — the tail points back to head.

The same algorithm applied to a partially circular list (where only part of the list forms a loop) finds the cycle entry point:

// Floyd's Cycle Detection — O(n) time, O(1) space
function detectCycle(head) {
  if (!head || !head.next) return null;

  let slow = head, fast = head;

  // Phase 1: Find meeting point inside the cycle
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  if (!fast || !fast.next) return null;  // no cycle

  // Phase 2: Find cycle entry point
  // Mathematical proof: distance from head to entry = distance from meeting point to entry
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow;  // cycle entry node
}

// Find cycle length
function cycleLength(head) {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Count steps to return to meeting point
      let length = 1;
      fast = fast.next;
      while (fast !== slow) { fast = fast.next; length++; }
      return length;
    }
  }

  return 0;  // no cycle
}

// For a true circular list, cycleLength equals the list length
console.log(cycleLength(a)); // 3 (our 3-node circular list)

Doubly Circular Linked List

The doubly circular variant adds a prev pointer to each node and connects head.prev to tail and tail.next to head. This enables O(1) deletion of any node (given a reference to it) and backward traversal.

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

  append(val) {
    const node = new DoublyNode(val);
    if (!this.head) {
      this.head = node;
      node.next = node;
      node.prev = node;
    } else {
      const tail = this.head.prev;  // tail = head.prev in doubly circular
      tail.next = node;
      node.prev = tail;
      node.next = this.head;
      this.head.prev = node;
    }
    this.size++;
  }

  // Delete any node — O(1) given node reference
  deleteNode(node) {
    if (this.size === 1) { this.head = null; this.size--; return; }
    node.prev.next = node.next;
    node.next.prev = node.prev;
    if (node === this.head) this.head = node.next;
    this.size--;
  }

  toArray() {
    if (!this.head) return [];
    const result = [];
    let cur = this.head;
    do { result.push(cur.val); cur = cur.next; } while (cur !== this.head);
    return result;
  }
}

const dcl = new DoublyCircularList();
dcl.append(1); dcl.append(2); dcl.append(3);
console.log(dcl.toArray()); // [1, 2, 3]
console.log(dcl.head.prev.val); // 3 (tail is head.prev)
console.log(dcl.head.next.next.next === dcl.head); // true (circular!)

Note

The LRU Cache data structure uses a doubly circular linked list internally (via a sentinel/dummy head node) combined with a hash map. The circular doubly linked list enables O(1) move-to-front and O(1) eviction of the least recently used node.

Complexity Summary

Operation	Singly Circular (tail ptr)	Doubly Circular
Insert at head	O(1)	O(1)
Insert at tail	O(1)	O(1)
Insert after node	O(1)	O(1)
Delete head	O(1)	O(1)
Delete tail	O(n)	O(1)
Delete given node	O(n)	O(1)
Search by value	O(n)	O(n)
Traverse all n nodes	O(n)	O(n)