JavaScript連結串列節點插入程式

---

連結串列是資料結構，長度可變，任何節點都可以被刪除或新增到連結串列中。在本教程中，我們將實現一個完整的程式，用於在連結串列中插入節點。

在連結串列中，我們可以新增新節點的三個不同位置：在首節點之前、在尾節點之後以及在連結串列的中間。

讓我們首先了解問題陳述：

示例場景：

Input 1: list = 1 -> 2 -> 3 -> 4 -> 5 -> null;
Input 2: node = 7;
Output 1: at start = 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
Output 2: at middle = 1 -> 2 -> 3 -> 7 ->  4 -> 5 -> null
Output 3: at end = 1 -> 2 -> 3 -> 4 -> 5 -> 7 ->  null 

在連結串列開頭新增節點

要在連結串列開頭新增節點，我們必須建立新節點並將連結串列的頭作為新節點的下一個節點，然後將頭指向新節點，從而在開頭將新節點新增到連結串列。

示例

下面給出了一個展示如何在連結串列中插入節點的 JavaScript 程式：

// 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")

執行上述程式碼後，您將得到以下結果：

Linked List after adding a node at starting: 
7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 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")

執行此程式碼後，您將得到以下結果：

Linked List after adding node in middle:
1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

上述程式碼的時間複雜度為O(N)，因為我們必須移動到要在其之前新增新節點的節點。上述過程的空間複雜度為O(1)，因為我們沒有使用任何額外的空間。

在連結串列末尾新增節點

要在連結串列末尾新增節點，我們必須建立一個新節點，並在尾節點之後新增該節點，然後將尾節點移動到下一個節點。

示例

在這個 JavaScript 程式中，我們使用上面討論的方法在連結串列末尾插入節點。

// 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")

此程式碼將產生以下輸出：

Linked List after adding node in middle:
1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null

上述程式碼的時間複雜度為O(1)，因為我們只需要移動一個指標，同樣也沒有使用額外的空間，因此空間複雜度為O(1)。