双链表元素删除的时间复杂性? [英] 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屋！