在单链表和双链表中进行删除的时间复杂度是多少？

Question

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

My understanding is that we need to traverse to node to know the previous pointer of the node and next pointer of node in singly linked list. The time complexity for singly linked list to delete is O(n) as a result.

For doubly linked list, since we know the previous and next pointers of the node we want to delete, the time complexity is 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天真地完成了对单个链接列表的处理，对于每个链接列表，它的工作量更大（如“定位要删除的节点”然后“在该节点之前找到节点”）。

但是通常情况下，您不会这样做。您的delete函数将在前进时记住上一个节点，这样，一旦找到要删除的节点，您还将在其之前有一个节点，因此您无需进行其他搜索。

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

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