資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究JavaScript編寫函式獲取連結串列中第N個節點的程式
連結串列是一種線性資料結構，所有節點透過儲存下一個節點的地址相互連線。查詢連結串列中的第n個節點意味著獲取給定連結串列中第n個節點的值，這可以透過兩種方法實現：迭代方法和遞迴方法。
示例
Given linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Node to find: 3
輸出
3
解釋：第三個節點的值為3。
迭代方法
在這種方法中，我們將使用while迴圈直接遍歷連結串列，直到到達最後一個節點或所需的節點。
示例
// 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);
}
輸出
The given linked list is: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null The value present at the nth node is: 5
時間和空間複雜度
上述程式碼的時間複雜度為O(N)，其中N是給定連結串列的大小。這裡給定的數字可能小於給定連結串列的大小，但在最壞的情況下，我們只會遍歷到連結串列的長度。
我們在這裡沒有使用任何額外空間，這意味著上述程式碼的空間複雜度為O(1)。
遞迴方法
在這種方法中，我們將使用遞迴呼叫而不是while迴圈遍歷連結串列，並實現之前的邏輯。
示例
// 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);
}
輸出
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
時間和空間複雜度
上述程式碼的時間和空間複雜度相同，均為O(N)，其中N是給定連結串列中的節點數。這裡的空間複雜度是由於遞迴呼叫造成的。
結論
在本教程中，我們實現了一個JavaScript程式來查詢給定連結串列中的第n個節點。如果第n個節點不存在，則列印“不存在”，否則列印該節點的值。我們實現了兩種方法，一種是使用while迴圈的迭代方法，另一種是遞迴方法。兩種方法的時間複雜度均為O(N)，但迭代方法更好，因為它不佔用額外空間。
更新於：2023年5月4日
92 次瀏覽
廣告