双向链表中节点删除的时间复杂度

为什么双向链表（O（1））中节点删除的时间复杂度比单向链表（O（n））中的节点删除快？双向链表中节点删除的时间复杂度

作业？编写从单个链接列表中删除节点的代码，然后就会很明显。 – 2009-12-13 06:53:06

我认为在标题中不应该有像dll这样的缩写，但我想不出更好的缩写。 – 2009-12-13 07:08:40

它与修复正在删除的节点之前的节点中的下一个指针的复杂性有关。

2009-12-13 06:53:51

因为你不能向后看...

2009-12-15 03:15:29 Paul

问题假定节点被删除是已知的，一个指向该节点是可用的。

为了删除节点并将上一个节点和下一个节点连接在一起，您需要知道它们的指针。在双向链表中，两个指针在要删除的节点中可用。在这种情况下时间复杂度是恒定的，即O（1）。

而在单链表中，指向前一个节点的指针是未知的，只能通过从头开始遍历列表直到它到达具有指向要删除的节点的下一个节点指针的节点。这种情况下的时间复杂度是O（n）。

如果仅通过值知道要删除的节点，则必须搜索该列表，并且在单向链接和双向链接列表中时间复杂度变为O（n）。

2013-05-02 06:17:14 Raj

这对于从单个链接列表中移除需要O（n）复杂性的节点而言是不正确的 - 请参阅下面的答案。有一个技巧，您可以从被删除的节点复制下一个节点的值，然后跳过该节点以指向节点，从而消除了遍历列表的任何需要。 – Ben 2017-10-07 07:17:42

在已知位置插入和删除是O（1）。然而，找到那个位置是O（n），除非它是列表的头部或尾部。

当我们谈论插入和删除复杂性时，我们通常假设我们已经知道将会发生什么。

2014-11-17 07:51:10 Tony

除非要删除的元素是头（或第一个）节点，否则我们需要遍历要删除的节点之前的节点。因此，在最坏的情况下，即当我们需要删除最后一个节点时，指针必须一路走到第二个节点，从而遍历（n-1）个位置，这给我们的时间复杂度为O（n）。

2016-08-05 06:40:16

实际上单链表中的删除也可以在O（1）中实现。

给定一个单向链表具有以下状态：

SinglyLinkedList: 
    Node 1 -> Node 2 
    Node 2 -> Node 3 
    Node 3 -> None 

    Head = Node 3

我们可以以这样的方式实现delete Note 2：

Node 2 Value <- Node 3 Value 
Node 2 -> None

在这里，我们与它的未来价值取代Node 2值节点（Node 3），并将其下一个值指针设置为Node 3（None）的下一个值指针，跳过现在有效的“重复”Node 3。因此不需要遍历。

2017-10-07 01:21:32 Ben

回答