2023在链表中插入节点的 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)。