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)。