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

在链表的中间添加节点

示例

要在链表中间添加节点，我们需要创建新的节点，并将要添加的新节点的前一个节点作为新节点的next节点，这样就在链表中间添加了新节点。

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