为什么从双向链表中删除节点比从单向链表中删除节点更快？

Question

我很好奇为什么从双向链表中删除节点要比从单向链表中删除快。根据我的讲座，从双向链表中删除节点只需要O(1)的时间，而从单向链表中则需要O(n)的时间。按照我的思路，它们两个都应该是O(n)，因为你可能需要遍历所有的元素，这取决于链表的大小。

我理解这与每个节点都有一个指向前一个节点和下一个节点的指针有关，但我不明白如何在O(1)的时间内完成这一操作。

- James Wilks

---

可能是单向链表和双向链表中节点删除的时间复杂度的重复问题。 - drs

Answer 1

这部分要根据你对设置的解释来部分理解。以下是两个不同版本。

版本1：假设你想从单向或双向链表中删除包含特定值x的链表节点，但你不知道它在链表中的位置。在这种情况下，你必须遍历整个链表，从头开始，直到找到要删除的节点。在单向链表和双向链表中，你可以以O（1）的时间删除它，因此总运行时间为O（n）。话虽如此，在单向链表中进行删除步骤更难，因为你需要更新前一个格子中的指针（该指针没有被要删除的格子所指向），因此你需要在此过程中存储两个指针。

版本2：现在，假设你获得了一个指向要删除的格子的指针，并且需要将其删除。在双向链表中，你可以使用下一个和上一个指针来识别该格子周围的两个格子，然后重新连接它们以将该格子从列表中拼接出来。这需要O(1)的时间。但是单向链表怎么办？为了从列表中删除这个格子，你必须更改出现在要删除的格子之前的格子的下一个指针，使其不再指向要删除的格子。不幸的是，由于该列表仅单向连接，你没有指向那个格子的指针。因此，你必须从链表开始，沿着节点向下走，并找到位于要删除节点之前的节点。这需要O(n)的时间，因此最坏情况下，删除步骤的运行时间为O(n)，而不是O(1)。(话虽如此，如果你知道两个指针——要删除的格子和它前面的格子，那么你可以以O(1)的时间删除该格子，因为你不必扫描列表来查找前一个格子。)

简而言之：如果您事先知道要删除的单元格，则双向链表允许您在O(1)的时间内删除它，而单向链表需要O(n)的时间。 如果您不事先知道单元格，则对于两种情况都需要O(n)的时间。

希望这有所帮助！

- templatetypedef

---

@arshajii- 我实际上是指O(1)，但这很模糊。删除节点的实际步骤是O(1)，但需要先进行O(n)的工作来找到它。我刚刚编辑了答案以澄清这一点。 - templatetypedef

非常感谢！如果我理解正确的话，这需要O(n)（最坏情况）的时间复杂度，因为在单链表中，一旦我们找到元素，我们就没有对前一个节点的引用，所以我们无法更改它的下一个节点并将其从列表中删除，因此我们必须再次遍历列表以获取该前一个单元格的指针。 - James Wilks

@JoshHamet- 如果你只知道要删除的节点，但不知道它前面的节点，那么你只需要进行遍历即可。 - templatetypedef

Answer 2

列表不必按顺序遍历以在双向链表中将前一个节点连接到下一个节点。您只需指向 curr.Prev.Next = curr.Next 和 curr.Next.Prev = curr.Prev。

在单向链表中，您必须遍历列表以查找前一个节点。在非排序列表中，遍历可能是 O(n)。

- Keith Payne

Answer 3

一个替代方法似乎是使用双指针，如这篇优秀资源中所概述的：https://github.com/mkirchner/linked-list-good-taste。这意味着你不需要跟踪当前和前一个指针，因为你只使用一个指向指针的单个指针，可以直接进行就地修改。如果我说错了，请告诉我，因为我刚学会这个。

- Tommaso Pappagallo