jsschools

Circular Linked List

A linked list where the tail node's next pointer points back to the head, forming a closed loop.

Spec ↗

Syntax

class CNode { constructor(val) { this.val = val; this.next = null; } }
// tail.next === head always (when non-empty)

Parameters

NameTypeRequiredDescription
tail CNode | null No Keeping a reference to the tail (rather than the head) lets you access both ends in O(1): tail for append, tail.next for head.

Returns

CircularLinkedList — A new circular linked list instance.

Examples

class CNode {
  constructor(val) { this.val = val; this.next = null; }
}
class CircularLinkedList {
  constructor() { this.tail = null; this.size = 0; }
  append(val) {
    const node = new CNode(val);
    if (!this.tail) { node.next = node; this.tail = node; }
    else { node.next = this.tail.next; this.tail.next = node; this.tail = node; }
    this.size++;
  }
  toArray() {
    if (!this.tail) return [];
    const out = [];
    let cur = this.tail.next; // head
    do { out.push(cur.val); cur = cur.next; } while (cur !== this.tail.next);
    return out;
  }
}
const cl = new CircularLinkedList();
cl.append('a'); cl.append('b'); cl.append('c');
console.log(cl.toArray());
Output 
[ 'a', 'b', 'c' ]

// Josephus problem: every k-th node removed
function josephus(n, k) {
  const cl = new CircularLinkedList();
  for (let i = 1; i <= n; i++) cl.append(i);
  let cur = cl.tail.next; // start at head
  while (cl.size > 1) {
    for (let i = 0; i < k - 2; i++) cur = cur.next;
    cur.next = cur.next.next; // remove k-th
    cur = cur.next;
    cl.size--;
  }
  return cur.val;
}
console.log(josephus(7, 3)); // survivor
Output 
4

Notes

| Operation | Best | Avg | Worst | Space | |------------------|------|------|-------|-------| | Insert (tail) | O(1) | O(1) | O(1) | O(1) | | Insert (head) | O(1) | O(1) | O(1) | O(1) | | Delete (head) | O(1) | O(1) | O(1) | O(1) | | Search | O(1) | O(n) | O(n) | O(1) | Traversal must detect the cycle explicitly (compare cur !== head) to avoid infinite loops. Commonly used for round-robin scheduling and the Josephus problem.

See also