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

Question

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

Answer 1

该问题假定要删除的节点是已知的,并且指向该节点的指针可用.

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

而在单链接列表中,指向前一节点的指针是未知的,并且只能通过从头部遍历列表直到它到达具有指向要删除的节点的下一节点指针的节点来找到.在这种情况下,时间复杂度为O(n).

在仅通过值知道要删除的节点的情况下,必须搜索列表,并且在单链接和双链接列表中时间复杂度变为O(n).

从需要O（n）复杂性的单链列表中删除节点方面，这是不正确的-请参阅下面的答案。有一个技巧，您可以从要删除的节点中复制下一个节点的值，然后跳过该节点以指向该节点，这样就无需遍历列表。 (2认同)

Answer 2

实际上,单链表中的删除也可以在O(1)中实现.

给出具有以下状态的单链表:

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

   Head = Node 1

我们可以这样实现delete Node 2:

Node 2 Value <- Node 3 Value
Node 2 -> Node 4

在这里,我们将其值替换为Node 2下一个node(Node 3)的值,并将其下一个值指针设置为Node 3(Node 4)的下一个值指针,跳过现在有效的"重复" Node 3.因此不需要遍历.

有道理，但在删除最后一个元素时不会真正起作用，除非您有对前一个（倒数第二个）节点的引用。 (2认同)
@mangusta 那是不正确的。您所描述的是搜索操作后跟删除操作。删除操作已经知道要删除哪个节点。如果对常见数据结构的时间复杂度有疑问，请参考 bigocheatsheet.com。 (2认同)

Answer 3

因为你不能回头看...

Answer 4

在已知位置插入和删除的时间复杂度为 O(1)。然而，找到该位置的时间复杂度为 O(n)，除非它是列表的头或尾。

当我们谈论插入和删除复杂性时，我们通常假设我们已经知道这将发生在哪里。

Answer 5

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