双向链表元素删除的时间复杂度? [英] Time Complexity of Doubly Linked List Element Removal?

问题描述

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

A lot of what I'm reading says that removing an internal element in a doubly linked list (DLL) is O(1); but why is this the case?

我明白为什么 SLL 是 O(n)；遍历列表 O(n) 并删除 O(1) 但是你不是仍然需要在 DLL 中遍历列表来找到元素吗?

I understand why it's O(n) for SLLs; traverse the list O(n) and remove O(1) but don't you still need to traverse the list in a DLL to find the element?

推荐答案

对于双向链表，一旦知道元素在哪里，就会有固定的时间删除它.

For a doubly linked list, it's constant time to remove an element once you know where it is.

对于单向链表，一旦您知道元素和其前任的位置，就会有固定的时间删除该元素.

For a singly linked list, it's constant time to remove an element once you know where it and its predecessor are.

由于您指向的那个链接显示了一个单链表删除为 O(n) 和一个双链表删除 O(1)，所以可以肯定的是，一旦你已经知道要删除的元素的位置，但不其他任何东西.

Since that link you point to shows a singly linked list removal as O(n) and a doubly linked one as O(1), it's certain that's once you already know where the element is that you want to remove, but not anything else.

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

In that case, for a doubly linked list, you can just use the prev and next pointers to remove it, giving you O(1). Ignoring the edge cases where you're at the head or tail, that means something like:

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

但是，在单向链表中，您只知道要删除的节点，因此不能使用 corpse->prev 来获取它前面的节点，因为 没有 prev 链接.

However, in a singly linked list where you only know the node you want deleted, you can't use corpse->prev to get the one preceding it because there is no prev link.

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

You have to instead find the previous item by traversing the list from the head, looking for one which has a next of the element you want to remove. That will take O(n), after which it's once again O(1) for the actual removal, such as (again, ignoring the edge cases for simplicity):

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

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

That's why the two complexities are different in that article.

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

As an aside, there are optimisations in a singly-linked list which can make the deletion O(n) (the deletion being effectively O(1) once you've found the item you want to delete, and the previous item). In code terms, that goes something like:

# 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

这篇关于双向链表元素删除的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！