JavaScript program to count nodes in Circular linked list
A circular linked list is a type of linked list in which the last node is connected to the first node, creating a loop or circular structure. We will explore how to count nodes in a circular linked list.
Below are the approaches to count nodes in the Circular linked list:
Table of Content
- Iterative approach
- Recursive approach
Iterative approach
In this approach, we iterate over a circular linked list using a while loop. We start from the head node and traverse the list until we reach the head node again. In each iteration, we increment the counter to count the nodes. Once we reached the head node again we counted all the nodes in the circular linked list.
Example: The example below shows how to count nodes in a Circular linked list using an iterative approach.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
let head = null;
function add(data) {
const newNode = new Node(data);
if (!head) {
head = newNode;
newNode.next = head;
} else {
let current = head;
while (current.next != head) {
current = current.next;
}
current.next = newNode;
newNode.next = head;
}
}
function countNodesLoop() {
let current = head;
let count = 0;
if (head != null) {
do {
count++;
current = current.next;
} while (current != head);
}
return count;
}
add(1);
add(2);
add(3);
add(4);
console.log(countNodesLoop());
Output
4
Time Complexity: O(n)
Space Complexity: O(1)
Recursive approach
In this approach, define a recursive function. This function starts with the head node and recursively calls itself with the next node in the list. In each recursive call, the function increments a count variable to keep track of the number of nodes visited. This process continues until the base case is reached (base case occurs when the current node becomes same as the head node), at this point the function stops recursing and returns the final count.
Example: Below is the demonstration to count nodes in Circular linked list recursive approach.
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
let head = null;
function add(data) {
const newNode = new Node(data);
if (!head) {
head = newNode;
newNode.next = head;
} else {
let current = head;
while (current.next !== head) {
current = current.next;
}
current.next = newNode;
newNode.next = head;
}
}
function countNodes(current = head, count = 0) {
if (!head) {
return count;
}
if (current.next === head) {
return count + 1;
}
return countNodes(current.next, count + 1);
}
add(1);
add(2);
add(3);
add(4);
add(5);
console.log(countNodes());
Output
5
Time Complexity: O(n)
Space Complexity: O(n)