鏈表是具有不同長度的數據結構，任何節點都可以刪除或添加到鏈表中。在本教程中，我們將實現一個完整的程序，用于在具有空間和時間復雜度的鏈表中插入節點。讓我們首先了解問題陳述。
問題簡介
在給定的問題中，我們給出一個鏈表，由于我們可以通過在鏈表中添加或刪除節點來更改鏈表的大小，因此我們將在鏈表中添加或插入節點。
在鏈表中，我們可以在三個不同的位置添加新節點：最前面的節點、最后一個節點之后以及鏈表的中間。例如，給定的鏈表是 –
1 -> 2 -> 3 -> 4 -> 5 -> null，我們必須添加一個值為 9 的隨機節點。因此，有很多情況需要添加節點，例如 –
在起始處添加節點 – 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
在中間添加節點 – 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null
在末尾添加節點 – 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null
讓我們看看實現以下任務的方法 –
在鏈表開頭添加節點
示例
要在鏈表的開頭添加節點，我們必須創建新節點并將鏈表的頭作為下一個節點傳遞給新節點，然后將頭移動到新節點，添加新節點節點到鏈表的開頭。
// 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 add(data) {
var new_node = new Node(data);
new_node.next = head;
return new_node;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
head = add(7);
var data = 0;
while(head != null) {
data = data + head.value + " -> ";
head = head.next;
}
console.log("Linked List after adding a node at starting: ")
console.log(data + "null")
登錄后復制
上述代碼的時間復雜度為 O(1)，因為我們只需移動一個指針，同樣沒有使用額外的空間，使得空間復雜度為 O(1)。
在鏈表中間添加節點
示例
要在鏈表中間添加節點，我們必須創建新節點并傳遞該節點，然后才能將鏈表的新節點添加為新節點的下一個節點，這會添加新節點節點到中間的鏈表。
// 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 add(data,head) {
var new_node = new Node(data);
var temp = head;
while(temp.value != 3) {
temp = temp.next;
}
new_node.next = temp.next;
temp.next = new_node;
return head;
}
var head = new Node(1);
var tail = head;
tail = push(tail, 2)
tail = push(tail, 3)
tail = push(tail, 4)
tail = push(tail, 5)
head = add(7,head);
var data = 0;
while(head != null) {
data = data + head.value + " -> ";
head = head.next;
}
console.log("Linked List after adding node in middle:")
console.log(data + "null")
登錄后復制
上述代碼的時間復雜度是 O(N)，因為我們必須移動到需要添加新節點的節點。上述過程的空間復雜度是 O(1)，因為我們沒有使用任何額外的空間。
在鏈表末尾添加節點
示例
要在鏈表末尾添加節點，我們必須創建一個新節點，并將該節點添加到尾節點之后，并將尾節點移動到下一個節點。
// 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 add(data) {
var new_node = new Node(data);
tail.next = new_node;
tail = tail.next
return tail;
}
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 = add(7);
var data = 0;
while(head != null){
data = data + head.value + " -> ";
head = head.next;
}
console.log("Linked List after adding a node at the end: ")
console.log(data + "null")
登錄后復制
上述代碼的時間復雜度為 O(1)，因為我們只需移動一個指針，同樣沒有使用額外的空間，使得空間復雜度為 O(1)。
結論
在上面的教程中，我們學習了如何通過三種可能的方式在現有鏈表中添加新節點。我們已經看到了帶有解釋的正確代碼以及時間和空間復雜性。在鏈表中間添加一個節點需要 O(N) 時間，而對于其他兩種情況，其時間復雜度為 O(1)，并且對于所有三種可能性，空間復雜度都是 O(1)。
以上就是在鏈表中插入節點的 JavaScript 程序的詳細內容，更多請關注www.92cms.cn其它相關文章！
