为什么双链表(O(1))中节点删除的时间复杂度比单链表(O(n))中的节点删除更快?
该问题假定要删除的节点是已知的,并且指向该节点的指针可用。
为了删除节点并将前一个节点和下一个节点连接在一起,您需要知道它们的指针。在双向链表中,两个指针都在要删除的节点中可用。在这种情况下,时间复杂度是恒定的,即O(1)。
而在单链接列表中,指向前一节点的指针是未知的,并且只能通过从头部遍历列表直到它到达具有指向要删除的节点的下一节点指针的节点来找到。在这种情况下,时间复杂度为O(n)。
在仅通过值知道要删除的节点的情况下,必须搜索列表,并且在单链接和双链接列表中时间复杂度变为O(n)。
实际上,单链表中的删除也可以在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
。因此不需要遍历。
因为你无法向后看......
除非要删除的元素是头(或第一个)节点,否则我们需要在要删除的节点之前遍历该节点。因此,在最坏的情况下,即,当我们需要删除最后一个节点时,指针必须一直到第二个最后一个节点,从而遍历(n-1)个位置,这给了我们O(n)的时间复杂度。
它与修复您要删除的节点之前的节点中的下一个指针的复杂性有关。
在已知位置的插入和删除是O(1)。但是,找到该位置是O(n),除非它是列表的头部或尾部。
当我们谈论插入和删除复杂性时,我们通常假设我们已经知道将要发生的位置。
除非你知道必须删除的节点的地址,否则我不认为它是O(1).....你不循环到达必须从头部删除的节点吗?
它是O(1),前提是您拥有必须删除的节点的地址,因为您拥有它的上一节点链接和下一个节点链接。由于您拥有所有必需的链接,只需通过重新排列链接然后释放()它,将“感兴趣的节点”排除在列表之外。
但是在单个链表中你必须从头部遍历以获得它的前一个和下一个地址无论你是否有要删除的节点或节点位置的地址(如第1,第2,第10等, 。)被删除。