我非常清楚，当我们想要删除链表中的节点（无论是双链还是单链），并且我们必须搜索这个节点时，这个任务的时间复杂度是 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)，那么我的解决方案似乎有效。尽管在这一点上，仅使用双向链表可能是值得的:)