Why is removing a node from a doubly-linked list faster than removing a node from a singly-linked list?

Question

I was curious why deleting a node from a double linked list is faster than a single linked. According to my lecture, it takes O(1) for a double linked list compared to O(n) for a single linked. According to my thought process, I thought they both should be O(n) since you have to traverse across possibly all the elements so it depends on the size.

I understand it's going be associated with the fact that each node has a previous pointer and a next pointer to the next node, I just can't understand how it would be a constant operation in the sense of O(1)

Austerlitz

possible duplicate of Time complexity of node deletion in singly- and doubly-linked lists – Hexaemeron

Answer 1

This partially depends on how you're interpreting the setup. Here are two different versions.

Version 1: Let's suppose that you want to delete a linked list node containing a specific value x from a singly or doubly-linked list, but you don't know where in the list it is. In that case, you would have to traverse the list, starting at the beginning, until you found the node to remove. In both a singly- and doubly-linked list, you can then remove it in O(1) time, so the overall runtime is O(n). That said, it's harder to do the remove step in the singly-linked list, since you need to update a pointer in the preceding cell (which isn't pointed at by the cell to remove), so you need to store two pointers as you do this.

Version 2: Now let's suppose you're given a pointer to the cell to remove and need to remove it. In a doubly-linked list, you can do this by using the next and previous pointers to identify the two cells around the cell to remove and then rewiring them to splice the cell out of the list. This takes time O(1). But what about a singly-linked list? To remove this cell from the list, you have to change the next pointer of the cell that appears before the cell to remove so that it no longer points to the cell to remove. Unfortunately, you don't have a pointer to that cell, since the list is only singly-linked. Therefore, you have to start at the beginning of the list, walk downwards across the nodes, and find the node that comes right before the one to remove. This takes time O(n), so the runtime for the remove step is O(n) in the worst case, rather than O(1). (That said, if you know two pointers - the cell you want to delete and the cell right before it, then you can remove the cell in O(1) time since you don't have to scan the list to find the preceding cell.)

In short: if you know the cell to remove in advance, the doubly-linked list lets you remove it in time O(1) while a singly-linked list would require time O(n). If you don't know the cell in advance, then it's O(n) in both cases.

Hope this helps!

Auteur

@arshajii- I actually meant O(1), but it was ambiguous. The actual step of removing the node was O(1), but there's O(n) work done in advance to find it. I just edited the answer to clarify this. – Auteur

Thanks so much!! If i understood this right, it takes O(n) (worst case scenario) because in a single linked list once we find the element, we have no reference to the previous node so we cant change it's next removing it from the list so we have to traverse the list again to get that previous cells pointer – Austerlitz

@JoshHamet- You only need to do the traversal if you know the node to remove but don't know the node before it. – Auteur

Answer 2

The list does not have to be traversed in order to connect the previous node to the following node in a double-linked list. You simply point

curr.Prev.Next = curr.Next and curr.Next.Prev = curr.Prev.

In a single-linked list, you have to traverse the list to find the previous node. Traversal can be O(n) in a non-sorted list.

Hectic

Answer 3

An alternative approach seems to be to use double pointers as outlined in this excellent resource: https://github.com/mkirchner/linked-list-good-taste. This means you do not need to keep track of a current and previous pointer as you only use a single pointer to pointer that can modify in place directly. Please let me know if this is inaccurate as I just learnt this.

Emmi