在 JavaScript 中移除单链表中的元素

---

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

什么是单链表？

单链表由一系列节点组成。它是一种数据结构。其中每个节点包含一个值或我们可以称之为数据，以及指向序列中下一个节点的列表。列表中的第一个节点称为头部，列表中的最后一个节点指向 null，这表示列表的末尾。

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

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

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

当我们需要频繁地通过在开头或结尾添加或删除元素来更新或修改列表时，这些链接很有用。

理解问题

问题是给定一个链表，其中包含连接到每个后续值的元素。我们需要实现一个函数，该函数将从列表中删除指定的元素。例如，我们有一个像 1 -> 2 -> 3 -> 4 -> 5 这样的列表，这是一个链表，每个元素都连接到其下一个元素，我们需要删除该元素，假设我们要从列表中删除 4，因此删除 4 后，链表将如下所示：1 -> 2 -> 3 -> 5。

给定问题的逻辑

我们给定一个单链表，我们必须创建一个函数，该函数从列表中删除特定项目。为了解决此问题，我们将遍历链表。并从链表的头部开始。之后，我们将一次遍历一个节点，并执行此任务，直到我们没有找到要删除的节点或到达列表的末尾。

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

算法

步骤 1：由于我们必须从给定的链表中删除项目，因此首先我们将创建一个类来表示链表中的节点。此类将具有两个属性，如“数据”，用于存储节点的值，以及“下一个”，用于指向列表中的下一个节点。

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