JavaScript program to find the length of a linked list

The linked list is a linear data structure that can be variable in length. The length of the linked list can be changed. This is the problem that the length of the array in the array cannot be changed. In this article, we will find the length of a given linked list by implementing the code and checking edge cases. We will use while loop and class concept in this article.

Problem Introduction

In the given problem, we are given a linked list, first, we have to create the linked list using a class and then we have to find the length of the given linked list. Since the length of the linked list can change, we will find the length of the linked list at a specific code point.

We will use two methods, first is the direct iterative method using while loop and the other is the recursive method to find the length of the given linked list.

Iteration method

In this method, we will first create a linked list using a class to provide a structure for the linked list. We will define some functions, such as push function, to add values ​​to the linked list by simply passing headers and data.

Example

In this process, we will use a while loop, the head or starting node of the linked list, and a variable to count the number of nodes in the linked list, which is the length of the given linked list.

// creating the linked list node
class Node{
   constructor(data)  {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data){
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}
function length(head){
   temp = head;
   var count = 0
   while(temp != null) {
      count++;
      temp = temp.next;
   }
   return count;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))

In the method given above, we are not using any extra space and traversing the linked list only once. Therefore, the time complexity of the above method is O(N), where N is the size of the linked list, and the space complexity of the above method is O(1).

Recursive method

In this method we will follow the same steps as in the above method to create the linked list, for the main task we will use the recursive method.

Example

Calling the same function with different parameters and specific basic conditions than the function itself is called recursion. In this method we will call the function with the head of the linked list and then from that function we will call the function again but with the argument the next node from the current node. As a return value we will return 1 for the recursive call and the result will be given on the first call. Let's look at the code -

// creating the linked list node
class Node {
   constructor(data) {
      this.value = data;
      this.next = null;
   }
}
function push(tail, data) {
   var new_node = new Node(data);
   tail.next = new_node;
   tail = tail.next;
   return tail
}

function length(cur) {
   if(cur == null) return 0;
   return 1 + length(cur.next);
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
tail = push(tail, 6)
console.log("Length of the given linked list is: " + length(head))

Time and space complexity

The time complexity of the recursive method is O(N), where N is the number of nodes present in the given linked list. The space complexity of the above code is O(N) because there are N calls in total and for each call we have to maintain the current node stack.

in conclusion

In this tutorial, we learned how to find the length of a given linked list by implementing the code and studying edge cases. We used the while loop and class concept from this article in the first method and the recursive method to find the length in the second method. The time complexity of both methods is O(N), where N is the length of the linked list, while the space complexity of the recursive method is O(N) due to the stack size.

The above is the detailed content of JavaScript program to find the length of a linked list. For more information, please follow other related articles on the PHP Chinese website!