Menu
Because of doubly linked list property, you do not need to traverse and that's why time complexity of removing a node using reference will be O(1).
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.
For example, Time Complexity to insert element at front is O(1) in Singly Linked List but it is O(√N) for Doubly Linked List as we have to access the next element to set its previous address to the new element.
The time complexity for removal is only O(1) for a doubly-linked list if you already have a reference to the node you want to remove. Removal for a singly-linked list is only O(1) if you already have references to the node you want to remove and the one before.
I do not quite 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 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With