linked-list - 双向链表元素删除的时间复杂度？

Question

我在读的很多内容都说删除双向链表 (DLL) 中的内部元素是 O(1) ;但为什么会这样呢？

我明白为什么是 O(n)对于 SLL；遍历列表O(n)并删除 O(1)但是您不是仍然需要遍历 DLL 中的列表来查找元素吗？

Answer 1

对于双向链表，一旦知道元素的位置，就会有固定的时间删除它。

对于单向链表，一旦知道元素及其前身的位置，就会有固定的时间删除元素。

由于您指向的链接显示单链表删除为 O(n)和一个双重链接的 O(1) ，可以肯定的是，一旦您已经知道要删除的元素的位置，而不是其他任何内容。

在这种情况下，对于双向链表，您可以使用 prev和 next删除它的指针，给你 O(1) .忽略您处于头部或尾部的边缘情况，这意味着:

corpse->prev->next = corpse->next
corpse->next->prev = corpse->prev
free (corpse)

但是，在只知道要删除的节点的单向链表中，不能使用 corpse->prev得到它前面的一个，因为没有 prev关联。

您必须通过从头部遍历列表来找到前一项，寻找具有 next 的项。要删除的元素。这需要 O(n) ，之后又是 O(1)对于实际删除，例如(再次，为简单起见，忽略边缘情况):

lefty = head
while lefty->next != corpse:
    lefty = lefty-> next
lefty->next = corpse->next
free (corpse)

这就是为什么那篇文章中的两种复杂性不同的原因。

顺便说一句，单链表中有一些优化可以删除 O(n) (一旦找到要删除的项目和上一个项目，删除实际上是 O(1))。在代码方面，这类似于:

# Delete a node, returns true if found, otherwise false.

def deleteItem(key):
    # Special cases (empty list and deleting head).

    if head == null: return false
    if head.data == key:
        curr = head
        head = head.next
        free curr
        return true

    # Search non-head part of list (so prev always exists).

    prev = head
    curr = head.next
    while curr != null:
        if curr.data == key:
            # Found it so delete (using prev).

            prev.next = curr.next
            free curr
            return true

        # Advance to next item.

        prev = curr
        curr = curr.next

    # Not found, so fail.

    return false