Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Circular Linked Lists Operations

Explore the operations of circular linked lists including traversal, insertion, and deletion. Understand how to maintain the circular link during these operations, and learn efficient JavaScript implementations with attention to time and space complexity. This lesson equips you with practical skills to handle circular linked lists in real-world scenarios.

We'll cover the following...

At this stage, the difference between a circular linked list and a standard singly linked list is established. Instead of the last node pointing to NULL, it points back to the head node, forming a loop. As a result, the list has no natural termination point, and traversal requires explicit stopping conditions.

Now, let’s focus on the operations that can be performed on circular linked lists. While many of these operations are conceptually similar to those used in singly linked lists, there is an important difference: the circular connection must always be preserved.

Because the list forms a loop, operations such as traversal, insertion, and deletion must be implemented carefully. In particular:

  • Traversal cannot rely on reaching NULL to stop.

  • Insertions must ensure that the circular link remains intact.

  • Deletions must reconnect neighboring nodes so that the loop structure is maintained.

Traversal in a circular linked list

Traversal in a circular linked list is slightly different from traversal in a standard singly linked list. In a regular linked list, traversal stops when the current node becomes NULL. In a circular linked list, this stopping condition does not exist because the last node points back to the head.

Instead, traversal must stop when it returns to the starting node. Typically, the traversal steps are:

  1. Start traversal from the head node.

  2. Print the value stored in the current node.

  3. Move to the next node using current.next.

  4. Stop the traversal when the pointer reaches the head node again.

Let's look at the following interactive visualizer for circular linked list traversal.

JavaScript implementation of traversal in a circular linked list

The following code creates a simple circular linked list and traverses it once, stopping when the traversal returns to the head node.

Javascript (babel-node)
class ListNode {
    constructor(data) {
        this.data = data;
        this.next = null; // Points to the next node
    }
}
class CircularLinkedList {
    constructor() {
        this.head = null; // Points to the first node
    }
    traverse() {
        if (this.head === null) {
            console.log("The list is empty.");
            return;
        }
        let current = this.head; // Start from the head node
        while (true) {
            process.stdout.write(current.data + " -> "); // Process current node
            current = current.next; // Move to the next node
            if (current === this.head) { // Stop when traversal returns to head
                break;
            }
        }
        console.log(current.data + " (back to head)");
    }
}
// Create a circular linked list manually: 10 -> 20 -> 30 -> back to 10
const sampleList = new CircularLinkedList();
const first = new ListNode(10);
const second = new ListNode(20);
const third = new ListNode(30);
sampleList.head = first;
first.next = second;
second.next = third;
third.next = first; // Make the list circular
// Traverse the circular linked list
process.stdout.write("Traversal of circular linked list: ");
sampleList.traverse();
Doubly linked list traversal

  • Time complexity: O(n)O(n) because each node is visited once.

  • Space complexity: O(1)O(1) as traversal only uses a single pointer variable.

Insertion in a circular linked list

Insertion in a circular linked list is similar to the insertion in a singly linked list, but there is one extra requirement: the circular connection must remain intact.

Insertion at the beginning

In a normal singly linked list, inserting at the beginning mainly involves making the new node point to the current head and then updating the head. In a circular linked ...