JavaScript 从单链表中删除元素

在给定的问题陈述中，我们有一个单链表，我们的任务是从列表中删除一个元素。因此，我们将逐步讨论此操作。

什么是单链表

单链表由一系列节点组成，它是一种数据结构。在这个结构中，每个节点都包含一个值或者数据，并指向下一个节点。列表中的第一个节点称为头部，列表中的最后一个节点指向null，表示这是列表的结尾。

下面是一个单链表的可视化示例：

在上面的示例中，链表包含具有两个值的节点。第一个是数据部分，第二个是指向下一个节点的引用。这就是序列的形成方式。

单链表的主要特点是允许在列表的开始或给定节点之后高效地插入和删除元素。但是，在列表中间访问项或搜索值具有线性时间复杂度，需要从列表的末尾遍历列表。

当我们频繁更新或修改列表时，这些链接很有用，例如在列表的开头或结尾添加或删除元素。

理解问题

问题是给定一个包含连接到每个下一个值的元素的链表。我们需要实现一个函数，从列表中删除指定的元素。例如，我们有一个列表，如1 -> 2 -> 3 -> 4 -> 5，这是一个链表，每个元素都与其下一个元素相连接，我们需要删除元素，假设我们从列表中删除4，那么删除4之后，链表将变成1 -> 2 -> 3 -> 5。

给定问题的逻辑

我们有一个单链表，我们需要创建一个函数，从列表中删除指定的项。为了解决这个问题，我们将遍历链表。从链表的头部开始。然后我们一次遍历列表中的一个节点，并在找到要删除的节点或到达列表的末尾之前一直这样做。

然后，我们将通过检查是否找到要删除的项目来删除指定的项。如果在列表的头部找到要删除的节点，则更新头部为下一个节点。否则，在遍历列表时，我们将跟踪当前节点和上一个节点。如果找到要删除的节点，则更新上一个节点的引用以跳过要删除的节点。并返回更新后的链表。

步骤

步骤1 ：我们要从给定的链表中删除项，因此首先我们将创建一个类来表示链表中的节点。这个类将有两个属性，如’data’，用于存储节点的值，’next’，将指向列表中的下一个节点。

步骤2 ：创建节点后，我们将创建链表本身的类。它将有一个名为 head 的属性，它将指向列表中的第一个节点。如果列表为空，则将 head 设置为 null。

步骤3 ： 现在，我们将定义一个方法来向链表的节点添加项目。在这个方法中，我们将使用给定的数据创建一个新的节点，并将其添加到列表的末尾。每个新项目将被添加到链表的最后一个项目。

步骤4 ：由于我们需要执行给定的任务从列表中删除一个项目。因此，创建一个函数从列表中删除指定数据的项目。它将处理两种情况：第一种情况是，如果要删除的节点是头节点，则更新头引用以跳过当前头。否则，我们将遍历列表，同时保持当前节点和其前一个节点的跟踪，并继续进行此过程，直到找到要删除的节点为止。然后，我们将更新前一个节点的 next 引用以跳过当前节点。

步骤5 ：现在我们的任务是在删除节点后显示链表。我们将从头开始，并将每个节点的数据添加到一个数组中。最后，它将记录连接的数组项，并用箭头分隔。

示例

//Node in the linked list
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
// The linked list
class LinkedList {
   constructor() {
      this.head = null;
   }
   // Add items to the linked list
   add(data) {
      const newNode = new Node(data);

      if (!this.head) {
         this.head = newNode;
      } else {
         let current = this.head;
         while (current.next) {
            current = current.next;
         }
         current.next = newNode;
      }
   }
   // Remove item from the list  
   remove(data) {
      if (!this.head) {
         return;
      }

      if (this.head.data === data) {
         this.head = this.head.next;
         return;
      }

      let current = this.head;
      let previous = null;

      while (current && current.data !== data) {
         previous = current;
         current = current.next;
      }

      if (current) {
         previous.next = current.next;
      }
   }
   //Traverse and print the linked list
   display() {
      let current = this.head;
      let elements = [];

      while (current) {
         elements.push(current.data);
         current = current.next;
      }

      console.log(elements.join(" -> "));
   }
}

// Example
const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);

console.log("Before removal:");
list.display();

list.remove(3);

console.log("After removal:");
list.display();

输出

Before removal:
1 -> 2 -> 3 -> 4 -> 5
After removal:
1 -> 2 -> 4 -> 5

复杂度

从单链表中删除一个项的时间复杂度为O(n)，其中n是链表中的节点数。在最坏的情况下，这个时间可能会增加，因为我们需要遍历整个链表才能获取要删除的节点。空间复杂度为O(1)，因为我们在原地修改列表，不使用任何其他存储空间。

结论

在给定的问题中，我们专注于从单链表中删除特定的项。通过迭代列表并更新引用，我们可以有效地从列表中删除所需的项，时间复杂度为O(n)。