在鍊錶中插入節點的 JavaScript 程式

鍊錶是具有不同長度的資料結構，任何節點都可以刪除或新增到鍊錶中。在本教程中，我們將實作一個完整的程序，用於在具有空間和時間複雜度的鍊錶中插入節點。讓我們先了解問題陳述。

問題簡介

在給定的問題中，我們給出一個鍊錶，由於我們可以透過在鍊錶中新增或刪除節點來更改鍊錶的大小，因此我們將在鍊錶中新增或插入節點。

在鍊錶中，我們可以在三個不同的位置新增節點：最前面的節點、最後一個節點之後、鍊錶的中間。例如，給定的鍊錶是 -

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中文網其他相關文章！