25 - JavaScript - Circular LinkedList

A circular linked list is a data structure in which the nodes are connected in a circular fashion, forming a closed loop. Each node in the circular linked list contains a value and a pointer to the next node in the list. Unlike a traditional linked list, the last node in a circular linked list points back to the first node instead of null.

This circular structure offers some unique advantages over traditional linked lists. For example, since there is no "end" to the list, it is easy to traverse the entire list starting from any node. Additionally, inserting or deleting a node at the beginning or end of the list is simple and efficient, as the head and tail pointers only need to be updated.

A circular linked list is a type of linked list in which the last node of the list points to the first node instead of pointing to null. This creates a circular structure, hence the name "circular linked list".

In JavaScript, we can implement a circular linked list using objects and pointers. Each node in the list is an object that has a value property and a next property that points to the next node in the list. The last node in the list points to the first node, creating the circular structure.

Visualization Of Circular LinkedList

Here's a visual representation of a circular linked list:

+---------+    +---------+    +---------+    +---------+
| Node 1  | -> | Node 2  | -> | Node 3  | -> | Node 4  |
+---------+    +---------+    +---------+    +---------+
      ^                                                  |
      |                                                  v
   +---------+    +---------+    +---------+    +---------+
   | Head    | <- |         | <- |         | <- | Tail    |
   +---------+    +---------+    +---------+    +---------+

In the above figure, there are four nodes in the circular linked list, with each node having a value and a pointer to the next node. The last node (Node 4) points to the first node (Node 1), creating the circular structure.

The circular linked list also has two special nodes, the head and the tail. The head is a reference to the first node in the list, and the tail is a reference to the last node in the list. In this example, the head points to Node 1, and the tail points to Node 4.

Note that since this is a circular linked list, there is no concept of a "null" pointer. Instead, the last node points back to the first node, creating a cycle.

Syntax Of Circular Linked List

In JavaScript, the syntax for defining a circular linked list can be implemented using the class keyword. Here is an example of the syntax for a circular linked list:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  // methods for adding, removing, and manipulating nodes in the list
}

In this syntax, the Node class represents a single node in the circular linked list, with a value property to hold the data and a next property that points to the next node in the list.

The CircularLinkedList class represents the entire circular linked list and includes properties for the head and tail nodes, as well as a size property to keep track of the number of nodes in the list. This class also includes methods for adding, removing, and manipulating nodes in the list.

Note that the syntax for a circular linked list can vary depending on the programming language being used, but the basic structure of a circular linked list always involves nodes that point to each other in a circular fashion.

Code Examples

Following are the important operations supported by a circular list.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

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

  // Insert operation
  insert(data) {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
      this.tail = node;
      this.tail.next = this.head;
    } else {
      node.next = this.head;
      this.head = node;
      this.tail.next = this.head;
    }

    this.size++;
  }

  // Delete operation
  delete() {
    if (!this.head) {
      console.log("List is empty");
      return;
    }

    if (this.size === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      this.tail.next = this.head;
    }

    this.size--;
  }

  // Display operation
  display() {
    if (!this.head) {
      console.log("List is empty");
      return;
    }

    let current = this.head;
    do {
      console.log(current.data);
      current = current.next;
    } while (current !== this.head);
  }
}

// Create a new instance of CircularLinkedList
const myList = new CircularLinkedList();

// Insert some data
myList.insert("apple");
myList.insert("banana");
myList.insert("cherry");

// Display the list
myList.display();
// Output: 
// cherry
// banana
// apple

// Delete the first node
myList.delete();

// Display the list again
myList.display();
// Output: 
// banana
// apple

The CircularLinkedList class has three basic operations: insert(), delete(), and display().

1. insert() - This method inserts a new node at the beginning of the circular linked list. If the list is empty, it sets the head and tail pointers to the new node. If the list is not empty, it inserts the new node before the current head and updates the head pointer to point to the new node. The new node's next pointer is set to the old head node, and the tail node's next pointer is updated to point to the new head node.

2. delete() - This method removes the first node from the circular linked list. If the list is empty, it displays an error message. If the list has only one node, it sets the head and tail pointers to null. If the list has multiple nodes, it updates the head pointer to point to the second node and updates the tail node's next pointer to point to the new head node.

3. display() - This method displays the data of all nodes in the circular linked list. It starts at the head node and prints the data of each node until it reaches the tail node. Since it's a circular linked list, the loop stops when it reaches the head node again.

In the example code, we create a new instance of CircularLinkedList, insert some data, display the list, delete the first node, and display the list again. The output shows the data in the list before and after the deletion of the first node.

Summarizing Up

A circular linked list is a type of data structure in which each node has a pointer to the next node, and the last node points back to the first node, creating a circular loop. This data structure provides a way to traverse the list starting from any node and to loop through the list continuously. It can be used to implement circular buffers, hash tables, and scheduling algorithms. The basic operations supported by a circular linked list are insert, delete, and display. Insertion is performed at the start of the list, and deletion removes the first node from the list. Display operation prints the data of all nodes in the list.

One common use case for circular linked lists is in implementing circular buffers or queues. In a circular buffer, data is added to the buffer in a circular fashion, with new data overwriting old data when the buffer is full. The circular structure of the linked list makes it easy to implement this behavior, as the head and tail pointers can simply wrap around to the beginning of the buffer when they reach the end.

Overall, circular linked lists are a useful data structure in situations where a circular or cyclical relationship between data items needs to be represented.