在 JavaScript 中从单链表中删除元素
在给定的问题陈述中，我们会看到一个单链表，我们的任务是从列表中删除一个元素。因此，我们将在下面逐步讨论此操作。
什么是单链表?
单链表由一系列节点组成。它是一种数据结构。其中每个节点都包含一个值，或者我们可以说数据和列表到序列中的下一个节点。列表中的第一个节点称为头节点，列表中的最后一个节点指向 null，表示这是列表的末尾。
下面是单链表的可视化示例:
在上面的例子中，链表包含具有两个值的节点。第一个是数据部分，第二个是指向下一个节点的引用点。这就是序列的形成方式。
单链表的主要属性是它允许在列表的开头或给定节点之后高效地插入和删除。但访问列表中间的项目或搜索值具有线性时间复杂度，需要从末尾遍历列表。
当我们经常需要通过在开头或结尾添加或删除元素来更新或修改列表时，这些链接非常有用。
理解问题
问题是给定一个链接列表，其中包含与每个下一个值相连的元素。我们需要实现一个函数来从列表中删除指定的元素。例如，我们有一个列表，如 1 -> 2 -> 3 -> 4 -> 5，这是一个链接列表，每个元素都与其下一个元素相连，我们需要删除该元素，假设我们从列表中删除 4，因此删除 4 后，链接列表将看起来像 1 -> 2 -> 3 -> 5。
给定问题的逻辑
我们给出了一个单链表，我们必须创建一个函数来从列表中删除特定项目。为了解决这个问题，我们将遍历链表。从链表的头部开始。之后，我们将一次移动一个节点，并执行此任务，直到我们找不到要删除的节点或到达列表的末尾。
然后，我们将通过检查要删除的项目是否位于列表的头部来删除指定的项目，然后将头部更新为下一个节点。否则，我们将在遍历列表时跟踪当前节点和上一个节点。如果找到要删除的节点，则更新上一个节点的引用以跳过要删除的节点。并返回更新后的链表。
算法
步骤 1:因为我们必须从给定的链表中删除项目，所以首先我们将创建一个类来表示链表中的节点。这个类将具有两个属性，如"data"，用于存储节点的值和"next"，指向列表中的下一个节点。
步骤 2:创建节点后，我们将创建链接列表本身的类。它将具有一个名为 head 的属性，该属性将指向列表中的第一个节点。如果列表为空，则 head 将设置为 null。
步骤 3:现在我们将定义一个方法来将项目添加到链接列表的节点中。在此，我们将使用给定的数据创建一个新节点并将其附加到列表的末尾。每个新项目都将添加到链接列表的最后一项。
步骤 4:因为我们必须执行给定的任务来从列表中删除一个项目。因此，创建一个函数来从列表中删除具有指定数据的项目。它将处理两种情况，第一种情况是:如果要删除的节点是头部，则更新头部引用以跳过当前头部。否则，我们将遍历列表，同时跟踪当前节点及其前一个节点，并继续执行此过程，直到找不到要删除的节点。我们将更新前一个节点的下一个引用以跳过当前节点。
步骤 5:现在我们的任务是在删除节点后显示链接列表。我们将从头部开始，并将每个节点的数据附加到数组中。最后，它将记录连接的数组项，用箭头分隔。
示例
//链接列表中的节点
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// 链接列表
class LinkedList {
constructor() {
this.head = null;
}
// 将项目添加到链接列表中
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(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;
}
}
//遍历并打印链表
display() {
let current = this.head;
let elements = [];
while (current) {
elements.push(current.data);
current = current.next;
}
console.log(elements.join(" -> "));
}
}
// 示例
const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
console.log("删除前:");
list.display();
list.remove(3);
console.log("删除后:");
list.display();
输出
删除前: 1 -> 2 -> 3 -> 4 -> 5 删除后: 1 -> 2 -> 4 -> 5
复杂度
从单链表中删除一个项目的时间复杂度为 O(n)，其中 n 是列表中的节点数。在最坏的情况下，这个时间可能会增加，因为我们必须遍历整个列表才能找到要删除的节点。空间复杂度为 O(1)，因为我们在不使用任何其他存储的情况下就地修改列表。
结论
在给定的问题中，我们专注于从单链表中删除特定项目。通过迭代列表并更新引用，我们可以有效地从列表中删除所需项目，时间复杂度为 O(n)。
相关文章
有用资源
javascript 参考教程 - 该教程包含有关 javascript 的更多信息:https://www.cainiaomax.com/javascript/
