在鏈表中插入節點的 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)。