Why isn't deletion O(1) in both Singly Linked Lists and Doubly Linked Lists, when given the node to delete?

Question

It's abundantly clear to me that when we want to delete a node in a Linked List (be it doubly or singly linked), and we have to search for this node, the time complexity for this task is O(n), as we must traverse the whole list in the worst case to identify the node. Similarly, it is O(k) if we want to delete the k-th node, and we don't have a reference to this node already.

It is commonly cited that one of the benefits of using a doubly linked list over a singly linked list is that deletion is O(1) when we have a reference to the node we want to delete. I.e., if you want to delete the Node i, simply do the following: i.prev.next = i.next and i.next.prev = i.prev

It is said that deletion is O(1) in a singly linked list ONLY if you have a reference to the node prior to the one you want to delete. However, I don't think this is necessarily the case. If you want to delete Node i (and you have a reference to Node i), why can't you just copy over the data from i.next, and set i.next = i.next.next? This would also be O(1), as in the doubly linked list case, meaning that deletion is no more efficient in a doubly linked list in ANY case, as far as Big-O is concerned. Of course, this idea wouldn't work if the node you're trying to delete is the last node in the linked list.

It's really bugging me that no one remembers this when comparing singly and doubly linked lists. What am I missing?

To clarify: what I'm suggesting in the singly linked case is overwriting the data at the Node you want to delete, with the data from the next node, and then deleting the next node. This has the same desired effect as deleting Node i, though it is not what you're doing per se.

EDIT

What I've Learned:

So it seems that I am correct to some extent. First of all, many people mentioned that my solution isn't complete, as deletion of the last element is a problem, so my algorithm is O(n) (by definition of Big-O). I naively suggested in response to get around this by keeping track of the "2nd to last node" in your list - of course, this causes problems once the last node in your list has been deleted the first time. A solution that was suggested, and does seem to work, is to demarcate the end of your list with something like a NullNode, and I like this approach.

Other problems that were presented were referential integrity, and the time associated with copying the data itself from the next node (i.e. presumably, a costly deep copy might be necessary). If you can assume that you don't have other objects using the node that you're copying, and that the task of copying is O(1) in itself, then it seems like my solution works. Although, at this point, maybe its worth it to just use a Doubly Linked List :)

Answer 1

I was looking this up as a way to explain it and get references for a blog post.

Assuming you have to look up the node, like we do often with arrays and lists to find a value, you can only travel in one direction, and it will take O^n times in double and single link lists to get to the node and retrieve it's address in memory.

In a double linked list, once you have the nodes location you can set the pointers for the previous and the next node as needed without having to temporarily store any data. I think your idea would work, regardless of the last node issue, if while traversing to find the node in question that needs to be removed, a temp value, for the previous node is kept track of.

I think the real issue is in a single linked list you'd have to hold the node addresses in a temporary variable as you traverse to assign the new pointers. On each node, we'd have to store the current node as a previous, and the next node as the next so that pointer reassignment could be done, which is essentially what the double linked list does as it's created.

Even if we have to travel to the end node, if the previous is kept in a temporary variable, we could go back to assign a none to it's next pointer. But still, this is what the doubly linked list accomplishes my storing the addresses for it's neighbors, and then nothing has to go into a temporary state for the search and deletion.

Consider also that the O^n might not be the benefit, but in not having to place temporary data to do the removal. At the location of the node, we can access the neighbors in a doubly linked list, and in a single linked list, we would have to store data temporarily on each iteration for when the value is found. There's always the possibility the data would not be in the list. In a doubly linked list, the traversal would happen without having to store temporary information. What if there are parallel processes and that temporary data is changed before the pointer swap can happen? What happens if that temporary data is deleted before the new assignment?

Just some thoughts on it. Was hoping for a more thorough explanation myself. Wikipedia: https://en.wikipedia.org/wiki/Doubly_linked_list

Answer 2

Deletion for Single Link List

Assume that there is total 6 node. and the first node is indicating Head.

If you want to delete the first node then complexity will O(1) because you just need 1 iteration.

If you want to delete the 4th node then complexity will O(n)

If you want to delete the last node then complexity will O(n) because you have to iterate all the node.

Answer 3

It is true that copying data from i.next to i and then deleting i would be O(1) assuming that copying the data is also O(1).

But even with this algorithm, since deleting the last element is O(n), and a description of a function in terms of big O notation only provides an upper bound on the growth rate of the function, that means your algorithm is still O(n).

Regarding your comment:

I guess my dissatisfaction comes from the fact that textbooks and basically every resource online cites the #1 biggest advantage of doubly linked lists is deletion - this seems a little disingenuous. It's a very specific case of deletion - deletion at the tail! If efficient deletion is all you're going for, seems like this doesn't warrant using a doubly instead of a singly linked list (due to all the overhead necessary of having double the number of pointers). Simply store a reference to the second to last node in your list, and you're good to go!

You can certainly store a reference to the second to last node and make deletion of the last node O(1), but this would be the case only for the first time you delete the last node. You could update the reference to the node before it, but finding it will be O(n). You can solve this if you keep a reference to second to last element, and so on. At this point, you have reasoned your way to a doubly linked list, whose main advantage is deletion, and since you already have pointers to previous nodes you don't really need to move values around.

Remember that big O notation talks about the worst case scenario, so if even a single case is O(n) then your entire algorithm is O(n).

When you say a solution is O(n) you are basically saying "in the worst possible case, this algorithm will grow as fast as n grows".

Big O does not talk about expected or average performance, and it's a great theoretical tool, but you need to consider your particular use cases when deciding what to use.

Additionally, if you need to preserve reference integrity, you would not want to move values from one node to the other, i.e. if you tad a reference to node i+1 and delete node i, you wouldn't expect your reference to be silently invalid, so when removing elements the more robust option is to delete the node itself.

Answer 4

Nice question.

Simple answer: The alternate solution you are suggesting for singly linked lists is not complete and fails when you are given the last node for deletion. There is no way that you can make the previous to last node point to null.

Hence, for a valid solution, the complexity in case of deletion in the singly linked list is O(n).

Answer 5

The problem with this approach is that it invalidates the wrong reference. Deleting the node shall only invalidate a reference to that node, while the references to any other node shall remain valid.

As long as you do not hold any reference to the list, this approach would work. Otherwise it is prone to failure.

Answer 6

It is said that deletion is O(1) in a singly linked list ONLY if you have a reference to the node prior to the one you want to delete. However, I don't think this is necessarily the case. If you want to delete Node i (and you have a reference to Node i), why can't you just copy over the data from i.next, and set i.next = i.next.next?

Because it is the previous node's "next" member that you want to set equal to what i.next points to before you delete i. Finding the previous node is an O(N) operation for single-linked list, if you don't have a reference to it. For a double-linked list, finding the previous node is a O(1) operation as it should be i.prev

Answer 7

For a node in the middle of the list you need to modify the previous node (so its "next" pointer is pointing to the removed nodes "next").

With a double-linked list it's simple since the node to delete contains a pointer to the previous node. That's not possible with s single-linked list, where you need to iterate over list until you find a node whose "next" pointer is the node to delete.

Therefore removing a node in a double-linked list is O(1). And for a single-linked list it's O(n), where n is the number of nodes before the node you want to remove.