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

Question

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

Answer 1

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

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

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

如果仅通过值知道要删除的节点，则必须搜索列表，并且无论是单链表还是双链表，时间复杂度都变为 O(n)。

Answer 2

实际上单链表的删除也可以在 O(1) 内实现。

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

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

   Head = Node 1

我们可以通过以下方式实现删除节点 2：

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

这里我们将节点 2 的值替换为其下一个节点的值(Node 3) 并将其下一个值指针设置为 Node 3 (Node 4) 的下一个值指针，从而有效地跳过现在的“重复”节点 3。因此不需要遍历。

Answer 3

因为你无法回头看...

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

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

如果您拥有必须删除的节点的地址，那么它的复杂度是 O(1)，因为您拥有它的上一个节点链接和下一个节点链接。
由于您拥有所有必要的链接，只需通过重新排列链接将“感兴趣的节点”从列表中删除，然后 free() 它即可。

但是在单个链表中，您必须从头开始遍历才能获取它的上一个和下一个地址，无论您是否有要删除的节点的地址或节点位置（如第 1 个、第 2 个、第 10 个等）， .) 待删除。

Answer 8

假设有一个从 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)

2. 单链表
   由于单链表中没有前一个指针，因此无法向后移动，因此必须从头开始遍历列表

Node* temp = head;
while(temp->next != givenNode)
{
  temp = temp->next;
}
temp->next = givenNode->next;

时间复杂度 = O(N)

Answer 9

在LRU缓存设计中，双向链表中的删除需要O(1)时间。 LRU缓存是通过哈希图和双向链表实现的。在双向链表中，我们存储值，它的哈希映射存储链表节点的指针。

如果缓存命中，我们必须将元素移动到列表的前面。如果节点位于双向链表中间的某个位置，由于我们将指针保留在哈希映射中并且我们在 O(1) 时间内检索，我们可以通过将

  next_temp=retrieved_node.next
  prev_temp=retrieved_node.prev

指针设置为 None 来

  retrieved_node.next=None
  retrieved_node.prev=None

删除它，然后您可以重新连接丢失的节点链表的一部分

 prev_temp.next=next_temp