链表是具有不同长度的数据结构，任何节点都可以删除或添加到链表中。在本教程中，我们将实现一个完整的程序，用于在具有空间和时间复杂度的链表中插入节点。让我们首先了解问题陈述。
问题简介
在给定的问题中，我们给出一个链表，由于我们可以通过在链表中添加或删除节点来更改链表的大小，因此我们将在链表中添加或插入节点。
在链表中，我们可以在三个不同的位置添加新节点：最前面的节点、最后一个节点之后以及链表的中间。例如，给定的链表是 -
1 -> 2 -> 3 -> 4 -> 5 -> null，我们必须添加一个值为 9 的随机节点。因此，有很多情况需要添加节点，例如 -
-
在起始处添加节点 - 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
立即学习“Java免费学习笔记（深入）”；
在中间添加节点 - 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)。
