JavaScript program for writing a function to get the Nth node in a linked list

A linked list is a linear data structure in which all nodes are connected to each other by storing the address of the next node. Finding the nth node in a linked list means getting the value of the nth node in a given linked list, which can be done by both iterative and recursive methods.

Example

Given linked list: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Node to find: 3

Output

3

Explanation: The value of the third node is 3.

Iteration method

In this method, we will directly traverse the linked list using while loop until we reach the last node or the desired node.

Example

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);
}

// function to find the nth node 
function findNode(head, node){
   var temp = head;
   while(node > 1 && temp != null){
      node--;
      temp = temp.next;
   }
   return temp;
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 5;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the Nth Node");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

Output

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The value present at the nth node is: 5

Time and space complexity

The time complexity of the above code is O(N), where N is the size of the given linked list. The number given here may be smaller than the size of the given linked list, but in the worst case we will only traverse the length of the linked list.

Here we are not using any extra space, which means the time complexity of the above code is O(1).

Recursive method

In this method, we will use recursive calls instead of while loops to traverse the linked list and implement the previous logic.

Example

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   var ans = ""
   while(temp.next != null){
      ans += temp.value;
      ans += " -> "
      temp = temp.next
   }
   ans += temp.value
   ans += " -> null"
   console.log(ans)
}

// function to add data in linked list 
function add(data, head, tail){
   return tail.next = new Node(data);    
}

// function to find the nth node 
function findNode(head, node){
   if(node == 1){
      return head;
   }
   else if(head == null){
      return null;
   }
   else{
      return findNode(head.next, node-1);
   }
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)

// printing linked list 
console.log("The given linked list is: ")
print(head)

// defining node to get 
var node = 9;

// calling function to get the nth node; 
var nth_node = findNode(head,node)
if(nth_node == null){
   console.log("The given linked list does not have the " + node + " number of nodes");
}
else{
   console.log("The value present at the nth node is: " + nth_node.value);
}

Output

The given linked list is: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null
The given linked list does not have the 9 number of nodes

Time and space complexity

The time and space complexity of the above code are the same, both are O(N), where N is the number of nodes in the given linked list. The space here is due to recursive calls.

in conclusion

In this tutorial, we implemented a JavaScript program to find the nth node in a given linked list. If the nth node does not exist, then we print that it does not exist, otherwise we print the value that exists at that node. We implemented two methods, one is iterative using while loop and the other is recursive method. The time complexity of both is O(N), but iteration is better since it requires no extra space.

The above is the detailed content of JavaScript program for writing a function to get the Nth node in a linked list. For more information, please follow other related articles on the PHP Chinese website!