Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and…
Consider an implementation of unsorted single linked list. Suppose it has its representation with a head and a tail pointer (i.e. pointers to the first and last nodes of the linked list). Given the representation, which of the following operation can not be implemented in O(1) time?
Show answerHide answer
Correct answer: (D) Deletion of the last node of the linked list
Explanation
Although we have a tail pointer, it is of no use for deletion because there is no previous pointer. To delete the last node we need a pointer to the second-last node so that it can become the new last node; finding it requires traversing the whole list, which takes O(n) time.