Circular Linked List in JavaScript
1 What is a Circular Linked List?
The circular linked list is a linked list where all nodes are connected to form a circle. In a circular linked list, the first node and the last node are connected to each other which forms a circle. There is no NULL at the end.
There are generally two types of circular linked lists:
- Circular Singly Linked List: The last node contains a pointer to the first node of the list. We traverse the circular singly linked list until we reach the same node where we started.
- Circular Doubly Linked List: It has properties of both a doubly linked list and a circular linked list in which two consecutive elements are linked or connected by the previous and next pointer, and the last node points to the first node by the next pointer, and also the first node points to the last node by the previous pointer.
Representation of Circular Linked List
Circular linked lists are similar to single Linked Lists with the exception of connecting the last node to the first node.
class Node {
constructor(data = null) {
this.data = data;
this.next = null;
}
setter(x) {
this.data = x;
}
}
// Simple circular linked list in javascript
let head = new Node();
head.setter(10);
head.next = new Node();
head.next.setter(20);
head.next.next = new Node();
head.next.next.setter(30);
// Connect last node to the first node to make it circular
head.next.next.next = head;2 Insert at Begin of Circular Linked List
Naive Method O(N)
We traverse to the last node, insert the new node after the last node, then make the next of the new node point to the head of the link list, and finally update the head.
function insertAtFrontNaive(head, newData) {
let newNode = new Node();
newNode.setter(newData);
if (head === null) {
newNode.next = newNode;
return newNode;
}
let curr = head;
while (curr.next !== head) {
curr = curr.next;
}
curr.next = newNode;
newNode.next = head;
return newNode; // New head
}Efficient Method O(1)
Instead of traversing, we can insert the new node just after the head node, and then swap the data between the head node and the newly inserted node. This achieves insertion at the front in O(1) time.
function insertAtFrontEfficient(head, newData) {
let newNode = new Node();
newNode.setter(newData);
if (head === null) {
newNode.next = newNode;
return newNode;
}
// Insert new node after head
newNode.next = head.next;
head.next = newNode;
// Swap data between head and new node
let temp = head.data;
head.data = newNode.data;
newNode.data = temp;
return head;
}3 Insert at the End of Circular Linked List
Naive Approach O(N)
Traverse to the last node and insert the new node after the last node. Then the next of the new node is made to point to the head of the link list.
function insertAtEndNaive(head, newData) {
let newNode = new Node();
newNode.setter(newData);
if (head === null) {
newNode.next = newNode;
return newNode;
}
let curr = head;
while (curr.next !== head) {
curr = curr.next;
}
curr.next = newNode;
newNode.next = head;
return head;
}Efficient Approach O(1)
We are not traversing to the last node. Instead, we attach the new node after head and interchange the data of head and the new node. After swapping, the new node becomes the new head, meaning the original head is now the last node!
function insertAtEndEfficient(head, newData) {
let newNode = new Node();
newNode.setter(newData);
if (head === null) {
newNode.next = newNode;
return newNode;
}
// Insert new node after head
newNode.next = head.next;
head.next = newNode;
// Swap data
let temp = head.data;
head.data = newNode.data;
newNode.data = temp;
// Move head pointer one step forward
return newNode;
}4 Delete Head of Circular Linked List
Naive Approach O(N)
Traverse to the last node, make its next point to the second node, and then update the head pointer.
function deleteHeadNaive(head) {
if (head === null) return null;
if (head.next === head) return null; // Only one node
let curr = head;
while (curr.next !== head) {
curr = curr.next;
}
curr.next = head.next;
return head.next;
}Efficient Method O(1)
Copy the data of the second node into the head node, and then delete the second node.
function deleteHeadEfficient(head) {
if (head === null) return null;
if (head.next === head) return null; // Only one node
// Copy data of next node to head
head.data = head.next.data;
// Delete the next node
head.next = head.next.next;
return head;
}5 Circular Doubly Linked List
A Circular Doubly Linked List has properties of both a doubly linked list and a circular linked list.
Insertion at the beginning of the list:
To insert a node at the beginning, we create a new node, point its next to the first node, and its prev to the last node. The last node's next points to the new node, and the first node's prev points to the new node. Finally, shift the head (Start) pointer to this new node.
class DoublyNode {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
function insertAtFrontCDLL(head, newData) {
let newNode = new DoublyNode();
newNode.data = newData;
if (head === null) {
newNode.next = newNode;
newNode.prev = newNode;
return newNode;
}
let last = head.prev;
// Update new node pointers
newNode.next = head;
newNode.prev = last;
// Update existing list pointers
last.next = newNode;
head.prev = newNode;
return newNode; // New node becomes the head
}