Time Complexity of Doubly Linked List Element Removal?

Question

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?

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?

Answer 1

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.

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.

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)

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.

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.

---

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

Answer 2

As it's stated where your link points to:

The cost for changing an internal element is based on already having a pointer to it, if you need to find the element first, the cost for retrieving the element is also taken.

So, for both DLL and SLL linear search is O(n), and removal via pointer is O(1).