Ama*_*nda 5 algorithm linked-list nodes data-structures
我非常清楚，当我们想要删除链表中的节点（无论是双链还是单链），并且我们必须搜索这个节点时，这个任务的时间复杂度是 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)，那么我的解决方案似乎有效。尽管在这一点上，仅使用双向链表可能是值得的:)
确实，将数据从i.next复制i到 然后删除i将O(1)假设复制数据也是O(1)。
但即使使用这个算法，由于删除最后一个元素是O(n)，并且用大 O 表示法对函数的描述仅提供了函数增长率的上限，这意味着您的算法仍然是O(n)。
关于您的评论：
我想我的不满来自于这样一个事实：教科书和基本上所有在线资源都引用了双向链表的第一大优点是删除 - 这似乎有点不诚实。这是一种非常特殊的删除情况——尾部删除！如果高效删除是您所追求的一切，似乎这并不能保证使用双链表而不是单链表（由于拥有双倍指针数量所需的所有开销）。只需存储对列表中倒数第二个节点的引用，就可以开始了！
您当然可以存储对倒数第二个节点的引用并删除最后一个节点O(1)，但只有第一次删除最后一个节点时才会出现这种情况。您可以更新对之前节点的引用，但找到的将是O(n). 如果保留对倒数第二个元素的引用，等等，则可以解决此问题。此时，您已经推理出了双向链表，其主要优点是删除，并且由于您已经拥有指向先前节点的指针，因此您实际上不需要移动值。
请记住，大O符号谈论的是最坏的情况，因此，如果即使是单个情况，O(n)那么您的整个算法也是O(n)。
当你说一个解决方案时，O(n)你基本上是在说“在最坏的可能情况下，这个算法的增长速度会和n增长一样快”。
BigO并不谈论预期或平均性能，它是一个很棒的理论工具，但在决定使用什么时，您需要考虑您的特定用例。
此外，如果您需要保留引用完整性，您不会希望将值从一个节点移动到另一个节点，即，如果您添加对节点的引用i+1并删除节点i，您不会期望您的引用默默地无效，因此当删除元素更可靠的选择是删除节点本身。