鍊錶是具有不同長度的資料結構，任何節點都可以刪除或新增到鍊錶中。在本教程中，我們將實作一個完整的程序，用於在具有空間和時間複雜度的鍊錶中插入節點。讓我們先了解問題陳述。
在給定的問題中，我們給出一個鍊錶，由於我們可以透過在鍊錶中新增或刪除節點來更改鍊錶的大小，因此我們將在鍊錶中新增或插入節點。
在鍊錶中，我們可以在三個不同的位置新增節點：最前面的節點、最後一個節點之後、鍊錶的中間。例如，給定的鍊錶是 -
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 程式的詳細內容。更多資訊請關注PHP中文網其他相關文章！
