The Answer given is A)
I think the naswer should be B) as we have both the prev pointer and the next pointer available , it will take constant time to update the adjacent nodes pointers and delete the given node .?
So does deletion include search time as well ?
I thought that the position of the node is already known and we have to only perform deletion.
So if this question comes in exam what do we consider ?
http://stackoverflow.com/questions/1895769/time-complexity-of-node-deletion-in-singly-and-doubly-linked-lists
For deletion=search time+link modification
When deleted node address is given then in CDLL we can perform deletion in O(1) time.
In SLL eventhough deleted node address given it takes O(n) time.
In the given question address is not specified so TC=O(n) otherwise it is O(1) only in CDLL but not DLL.
IN DLL also reaching last node it takes O(n) time in CLL with help of prev pointer at first node we can reach last in O(1)
If the pointer to the node to be deleted is given then worst case time complexity would be O(1). But since it is not given, we would have only pointer to the head. So before deleting we would have to search by traversing the LL. In worst case it might take O(n) and deleting would take only O(1).
Thus O(n).
3912 Points
1526 Points
1502 Points
1501 Points
1480 Points
1432 Points
1286 Points
1242 Points
1240 Points
1232 Points
418 Points
334 Points
272 Points
234 Points
230 Points
Gatecse
GO PDF 2018 Volume 1 is now available. It ...
Just read all discussion here