algorithm - 在单链表和双向链表中删除的时间复杂度是多少？

Question

如果我们不知道节点的位置，那么单向链表和双向链表是否都需要O(n)的时间来删除？

我的理解是单向链表需要遍历到节点才能知道节点的上一个指针和下一个节点指针。结果单链表删除的时间复杂度是O(n)。

对于双向链表，由于我们知道要删除的节点的前指针和后指针，时间复杂度是O(1)。

Answer 1

在这两种情况下定位一个节点都是O(n)(伪代码如下，在下面的所有情况下):

def locate(key):
    ptr = head
    while ptr != null:
        if ptr.key == key:
            return ptr
        ptr = ptr.next
    return null

---

删除双向链表中的一个节点只给定它的指针是O(1)，因为您可以很容易地到达前一个节点:

def del (ptr):
    if ptr == head: # head is special case
        head = ptr.next
        free ptr
        return

    ptr.prev.next = ptr.next
    free ptr

---

对于相同的条件(只有指针)，删除单链表中的节点是O(n)，因为您需要首先定位该节点在您要删除的那个之前:

def del (ptr):
    if ptr == head: # head is special case
        head = ptr.next
        free ptr
        return

    prev = head
    while prev.next != ptr:
        prev = prev.next
    prev.next = ptr.next
    free ptr

但是，两个O(n) 操作仍然是O(n)，因为它与节点数线性相关。

因此，删除一个您还没有指针的节点，在这两种情况下都是 O(n)，它只是为每个 n 完成的工作对于单链表来说会更大，如果你天真地这样做(如“找到要删除的节点”然后“找到那个节点之前的节点”)。

---

不过通常情况下，您不会那样做。您的删除功能会在前进时记住前一个节点，这样一来，一旦您找到要删除的节点，您也有它之前的节点，因此您需要进行另一次搜索。

这可能是这样的，我们实际上是在您要删除的元素之前搜索元素:

def del (key):
    if head == null: # no action on empty list
        return

    if head.key == key: # head is special case
        temp = head
        head = head.next
        free temp
        return

    prev = head
    while prev.next != null:
        if prev.next.key == key:
            temp = prev.next
            prev.next = temp.next
            free temp
            return
        prev = prev.next