Why is deleting in a single linked list O(1)?

Question

I do not quiet understand why deleting at the end of a single linked list goes in O(1) time, as the wikipedia article says.

A single linked list consists out of nodes. A node contains some kind of data, and a reference to the next node. The reference of the last node in the linked list is null.

--------------    --------------           --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
--------------    --------------           --------------

I indeed can remove the the last node in O(1). But in that case you don't set the reference of the newly last node, the previous one, to null since it still contains the reference to the deleted last node. So I was wondering do they neglect that in the running time analysis? Or is it consired that you don't have to change that since the reference, well, just points to nothing, and such is seen as null?

Because if it would not be neglected I would argue that deleting is O(n). Since you have to iterate over the whole list to get to the newly last node and set its reference also to null. Only in a double linked list it would be really O(1).

-edit- Maybe this point of view gives some more clearence. But I see "deletion of a node" as succesfully deleting the node itself and setting the previous reference to null.

Answer 1

I am not sure I see in the Wikipedia article where it says that it's possible to remove the last entry of a singly-linked list in O(1) time, but that information is incorrect in most cases. Given any individual node in a linked list, it is always possible to remove the node after it in O(1) time by rewiring the list around that new node. Consequently, if you were given a pointer to the penultimate node in a linked list, then you could delete the last element of the list in O(1) time.

However, if you didn't have any extra pointers into the list other than a head pointer, then you could not delete the last element of the list without scanning to the end of the list, which would require Θ(n) time, as you have noted. You are absolutely correct that just deleting the last node without first changing the pointers into it would be a Very Bad Idea, since if you were to do this the existing list would contain a pointer to a deallocated object.

More generally - the cost to do an insertion or deletion in a singly-linked list is O(1), assuming you have a pointer to the node right before the one you want to insert or delete. However, you might have to do extra work (up to Θ(n)) to find that node.

Hope this helps!