algorithm - 当给定要删除的节点时，为什么在单链表和双链表中都没有删除 O(1)？

Question

我非常清楚，当我们想要删除链表中的一个节点（无论是双链还是单链），并且我们必须搜索这个节点时，这个任务的时间复杂度是 O(n)，因为我们必须在最坏的情况下遍历整个列表来识别节点。同样，如果我们要删除第 k 个节点，也是 O(k)，而且我们还没有对该节点的引用。

人们普遍认为，使用双向链表而不是单链表的好处之一是，当我们有一个要删除的节点的引用时，删除的时间是 O(1)。即，如果要删除节点 i，只需执行以下操作： i.prev.next = i.next 和 i.next.prev = i.prev

据说，仅当您对要删除的节点之前的节点有引用时，单链表中的删除是 O(1)。但是，我认为情况不一定如此。如果你想删除节点 i（并且你有对节点 i 的引用），为什么不能只复制 i.next 中的数据，然后设置 i.next = i.next.next？这也将是 O(1)，就像在双向链表的情况下一样，这意味着在任何情况下，在双向链表中删除都不会更有效，就 Big-O 而言。当然，如果您要删除的节点是链表中的最后一个节点，这个想法就行不通了。

在比较单链表和双链表时，没有人记得这一点，这真的让我很烦恼。我错过了什么？

澄清一下：我在单链接案例中的建议是用下一个节点的数据覆盖要删除的节点上的数据，然后删除下一个节点。这与删除 Node 具有相同的预期效果i，尽管它本身并不是您正在做的事情。

编辑

我学到了什么：

所以在某种程度上我似乎是正确的。首先，很多人提到我的解决方案并不完整，因为删除最后一个元素是一个问题，所以我的算法是 O(n)（根据 Big-O 的定义）。我天真地建议通过跟踪列表中的“倒数第二个节点”来解决这个问题 - 当然，一旦列表中的最后一个节点第一次被删除，这就会导致问题。一个建议并且似乎确实有效的解决方案是用 NullNode 之类的东西来划分列表的末尾，我喜欢这种方法。

出现的其他问题是引用完整性，以及与从下一个节点复制数据本身相关的时间（即，可能需要昂贵的深度复制）。如果您可以假设您没有其他对象使用您正在复制的节点，并且复制任务本身就是 O(1)，那么我的解决方案似乎有效。虽然，在这一点上，使用双向链表也许是值得的:)

标签： algorithmdata-structureslinked-listnodes

Answer 1

确实，将数据复制i.next到i然后删除i将O(1)假设复制数据也是O(1)。

但是即使使用这种算法，由于删除最后一个元素是O(n)，并且用大 O 表示法对函数的描述只提供了函数增长率的上限，这意味着你的算法仍然是O(n)。

关于您的评论：

我想我的不满来自于教科书和基本上所有在线资源都引用双向链表的 #1 最大优势是删除这一事实 - 这似乎有点虚伪。这是一个非常具体的删除案例——尾部删除！如果您只想进行高效删除，那么似乎这不保证使用双重而不是单链表（由于指针数量翻倍所需的所有开销）。只需在列表中存储对倒数第二个节点的引用，就可以开始了！

您当然可以存储对倒数第二个节点的引用并删除最后一个节点O(1)，但这只会在您第一次删除最后一个节点时出现。您可以更新对它之前的节点的引用，但找到它将是O(n). 如果您保留对倒数第二个元素的引用，则可以解决此问题，依此类推。至此，您已经推断出双向链表的方式，其主要优点是删除，并且由于您已经拥有指向先前节点的指针，因此您实际上不需要移动值。

请记住，大O符号表示最坏的情况，所以即使是单个情况，O(n)那么您的整个算法都是O(n).

当您说解决方案时，O(n)您基本上是在说“在最坏的情况下，该算法将随着增长而n增长”。

BigO没有谈论预期或平均性能，它是一个很好的理论工具，但在决定使用什么时，您需要考虑您的特定用例。

此外，如果您需要保持引用完整性，您不希望将值从一个节点移动到另一个节点，即如果您添加对 node 的引用i+1并删除 node i，您不会期望您的引用静默无效，所以当删除元素更强大的选择是删除节点本身。