我非常清楚，当我们想删除链表中的一个节点(无论是双链接还是单链接)，并且我们必须搜索这个节点时，这个任务的时间复杂度是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而言，在双链表中删除都不会更有效。当然，如果您要删除的节点是链表中的最后一个节点，那么这个想法是行不通的。
当比较单链表和双链表时，没有人记得这一点，这真的让我很困扰。我错过了什么？
为了澄清：在单链接的情况下，我建议用下一个节点的数据覆盖要删除的节点上的数据，然后删除下一个结点。这与删除节点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，则不会期望您的引用静默无效，因此在删除元素时，更稳健的选项是删除节点本身。
对于列表中间的节点，您需要修改上一个节点(因此其"下一个"指针指向已删除的节点"下一步")。
使用双链接列表很简单，因为要删除的节点包含指向上一个节点的指针。这在单链列表中是不可能的，您需要在列表上迭代，直到找到一个"下一个"指针是要删除的节点。
因此，删除双链表中的节点是O(1)。对于单个链表，它是O(n)，其中n是要删除的节点之前的节点数。
据说只有当您在要删除的节点之前有一个对该节点的引用。然而，我不认为情况一定如此。如果你想删除节点i(你有一个节点i的引用)，为什么你不能复制来自i.next的数据，并设置i.next=i.next.next？
因为它是上一个节点的"下一个"成员，您希望在删除i之前将其设置为i.next指向的值。如果您没有对其的引用，则查找上一个结点对于单链表是O(N)操作。对于双链表，查找上一节点是O(1)操作，因为它应该是i.prev
这种方法的问题在于它会使错误的引用无效。删除节点只能使对该节点的引用无效，而对任何其他的引用应保持有效。
只要您不持有对列表的任何引用，这种方法就会起作用。否则，它很容易失败。
问题不错。
简单的答案：您为单链表建议的替代解决方案不完整，当您得到最后一个要删除的节点时，它会失败。您无法使从上一个到最后一个节点指向null。
因此，对于有效的解决方案，在单链表中删除的情况下的复杂性是O(n)。
删除单个链接列表
假设总共有6个节点。并且第一节点指示Head。
如果你想删除第一个节点，那么复杂性将为O(1)，因为你只需要1次迭代。
如果你想删除第四个节点，那么复杂性将为O(n)
如果你想删除最后一个节点，那么复杂性将为O(n)，因为你必须迭代所有节点。
我查找它是为了解释它并获得博客文章的参考资料。
假设你必须查找节点，就像我们经常使用数组和列表来查找值一样，你只能朝一个方向移动，并且在双链接和单链接列表中需要O^n次才能到达节点并在内存中检索它的地址。
在双链接列表中，一旦有了节点位置，就可以根据需要设置上一个和下一个节点的指针，而无需临时存储任何数据。我认为，无论最后一个节点的问题如何，如果在遍历以找到需要删除的有问题的节点时，跟踪上一个节点上的临时值，您的想法都会奏效。
我认为真正的问题是在单个链表中，当你遍历以分配新指针时，你必须将节点地址保存在一个临时变量中。在每个节点上，我们必须将当前节点存储为前一个，将下一个节点存储为下一个，这样就可以进行指针重新分配，这基本上就是双链表在创建时所做的。
即使我们必须移动到结束节点，如果前一个保持在临时变量中，我们也可以返回给它的下一个指针赋值none。但是，这就是双链表所完成的，我为它的邻居存储地址，然后任何东西都不必进入搜索和删除的临时状态。
还要考虑O^n可能不是好处，但不必放置临时数据来进行删除。在节点的位置，我们可以访问双链表中的邻居，而在单链表中，我们必须在每次迭代中临时存储数据，以备找到值时使用。数据总是有可能不在列表中。在双链接列表中，遍历将在不必存储临时信息的情况下进行。如果存在并行进程，并且临时数据在指针交换发生之前发生了更改，该怎么办？如果在新分配之前删除了临时数据，会发生什么情况？
只是一些想法。我希望自己能有一个更彻底的解释。维基百科：https://en.wikipedia.org/wiki/Doubly_linked_list