JavaScript program for writing a function to get the Nth node in a linked list-JS Tutorial-php.cn

用于编写获取链表中第 N 个节点的函数的 JavaScript 程序

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

Copy after login

Output

Copy after login

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); }

Copy after login

Output

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

Copy after login

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); }

Copy after login

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

Copy after login

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!