The answer should be D)
What we can do is traverse from the head pointer to find object 1. Then change the node its pointing to object 3. Then we can free the Object 2.
The reason this algorithm is O(n) that we have to traverse from from the head node. To the node just before we want to delete (object 1) here.
Can’t it be done in O(1) by copying?
No, there has been a solution in which some say we swap object3 ↔ object2 and delete object2 node. But what we don’t consider here is the swapping complexity.
If the object that the node holds isn’t swappable O(1) then the complexity would depend upon the complexity to swap.
How O(1) in DLL?
- I arrive at Object2.
- Save the pointer to the next node.
- Traverse the link back to object 1 set the node next to object3.
- Free object2 node
Each step can be performed in O(1) hence its O(1)