鏈表是具有不同長(zhǎng)度的數(shù)據(jù)結(jié)構(gòu)，任何節(jié)點(diǎn)都可以刪除或添加到鏈表中。在本教程中，我們將實(shí)現(xiàn)一個(gè)完整的程序，用于在具有空間和時(shí)間復(fù)雜度的鏈表中插入節(jié)點(diǎn)。讓我們首先了解問(wèn)題陳述。
問(wèn)題簡(jiǎn)介
在給定的問(wèn)題中，我們給出一個(gè)鏈表，由于我們可以通過(guò)在鏈表中添加或刪除節(jié)點(diǎn)來(lái)更改鏈表的大小，因此我們將在鏈表中添加或插入節(jié)點(diǎn)。
在鏈表中，我們可以在三個(gè)不同的位置添加新節(jié)點(diǎn)：最前面的節(jié)點(diǎn)、最后一個(gè)節(jié)點(diǎn)之后以及鏈表的中間。例如，給定的鏈表是 –
1 -> 2 -> 3 -> 4 -> 5 -> null，我們必須添加一個(gè)值為 9 的隨機(jī)節(jié)點(diǎn)。因此，有很多情況需要添加節(jié)點(diǎn)，例如 –
在起始處添加節(jié)點(diǎn) – 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
在中間添加節(jié)點(diǎn) – 1 -> 2 -> 3 -> 7 -> 4 -> 5 -> null
在末尾添加節(jié)點(diǎn) – 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> null
讓我們看看實(shí)現(xiàn)以下任務(wù)的方法 –
在鏈表開(kāi)頭添加節(jié)點(diǎn)
示例
要在鏈表的開(kāi)頭添加節(jié)點(diǎn)，我們必須創(chuàng)建新節(jié)點(diǎn)并將鏈表的頭作為下一個(gè)節(jié)點(diǎn)傳遞給新節(jié)點(diǎn)，然后將頭移動(dòng)到新節(jié)點(diǎn)，添加新節(jié)點(diǎn)節(jié)點(diǎn)到鏈表的開(kāi)頭。
// 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")
登錄后復(fù)制
上述代碼的時(shí)間復(fù)雜度為 O(1)，因?yàn)槲覀冎恍枰苿?dòng)一個(gè)指針，同樣沒(méi)有使用額外的空間，使得空間復(fù)雜度為 O(1)。
在鏈表中間添加節(jié)點(diǎn)
示例
要在鏈表中間添加節(jié)點(diǎn)，我們必須創(chuàng)建新節(jié)點(diǎn)并傳遞該節(jié)點(diǎn)，然后才能將鏈表的新節(jié)點(diǎn)添加為新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，這會(huì)添加新節(jié)點(diǎn)節(jié)點(diǎn)到中間的鏈表。
// 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")
登錄后復(fù)制
上述代碼的時(shí)間復(fù)雜度是 O(N)，因?yàn)槲覀儽仨氁苿?dòng)到需要添加新節(jié)點(diǎn)的節(jié)點(diǎn)。上述過(guò)程的空間復(fù)雜度是 O(1)，因?yàn)槲覀儧](méi)有使用任何額外的空間。
在鏈表末尾添加節(jié)點(diǎn)
示例
要在鏈表末尾添加節(jié)點(diǎn)，我們必須創(chuàng)建一個(gè)新節(jié)點(diǎn)，并將該節(jié)點(diǎn)添加到尾節(jié)點(diǎn)之后，并將尾節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)。
// 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")
登錄后復(fù)制
上述代碼的時(shí)間復(fù)雜度為 O(1)，因?yàn)槲覀冎恍枰苿?dòng)一個(gè)指針，同樣沒(méi)有使用額外的空間，使得空間復(fù)雜度為 O(1)。
結(jié)論
在上面的教程中，我們學(xué)習(xí)了如何通過(guò)三種可能的方式在現(xiàn)有鏈表中添加新節(jié)點(diǎn)。我們已經(jīng)看到了帶有解釋的正確代碼以及時(shí)間和空間復(fù)雜性。在鏈表中間添加一個(gè)節(jié)點(diǎn)需要 O(N) 時(shí)間，而對(duì)于其他兩種情況，其時(shí)間復(fù)雜度為 O(1)，并且對(duì)于所有三種可能性，空間復(fù)雜度都是 O(1)。
以上就是在鏈表中插入節(jié)點(diǎn)的 JavaScript 程序的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注www.92cms.cn其它相關(guān)文章！
