25

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

4

8 回答 8

42

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

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

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

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

于 2013-05-02T06:17:14.470 回答
11

实际上，单链表中的删除也可以在 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 3) 的值，并将其下一个值指针设置为Node 3( Node 4) 的下一个值指针，跳过现在有效的“复制” Node 3。因此不需要遍历。

于 2017-10-07T01:21:32.140 回答
6

因为不能回头看...

于 2009-12-15T03:15:29.127 回答
4

在已知位置插入和删除是 O(1)。但是，找到该位置是 O(n)，除非它是列表的头部或尾部。

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

于 2014-11-17T07:51:10.270 回答
3

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

于 2009-12-13T06:53:51.037 回答
3

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

于 2016-08-05T06:40:16.847 回答
2

我不认为它的 O(1) 除非你知道必须删除的节点的地址.....你不要循环到达必须从头中删除的节点？？？？

如果您拥有必须删除的节点地址，则为 O(1)，因为您拥有它的 prev node link 和 next node link 。由于您拥有所有必要的链接，只需通过重新排列链接然后 free() 将“感兴趣的节点”从列表中删除。

但是在单个链表中，您必须从 head 遍历以获得它的上一个和下一个地址，无论您是否拥有要删除的节点的地址或节点位置（如第 1、2、10 等， .) 被删除。

于 2019-03-31T03:33:03.683 回答
1

假设有一个从 1 到 10 的链表，你必须删除节点 5，它的位置给你。

1 -> 2 -> 3 -> 4 -> 5-> 6-> 7-> 8 -> 9 -> 10

您必须将 4 的下一个指针连接到 6 才能删除 5。

  1. 双向链表你可以使用5上的前一个指针转到4。然后你可以做
4->next = 5->next;

或者

Node* temp = givenNode->prev;
temp->next = givenNode->next;

时间复杂度 = O(1)

  1. 单链表由于您在单链表中没有前一个指针，因此您不能向后移动，因此您必须从头遍历列表
Node* temp = head;
while(temp->next != givenNode)
{
  temp = temp->next;
}
temp->next = givenNode->next;

时间复杂度 = O(N)

于 2020-09-20T17:34:06.790 回答