Underflow condition in linked list may occur when attempting to
A. insert a new node when there is no free space for it
B. delete a non-existent node in the list
C. delete a node in empty list
D. insert a new node in the empty list
Answer: delete a node in empty list
Underflow condition in linked list may occur when attempting to delete an element from a empty linked list, or when deleting the last element of the list.
In general, deletion of an entry at any given location of a linked list requires that we first find the location where the entry is and then delete it. To find the entry we need to traverse the list starting at the beginning until we find the location where our entry is. So, finding a node in a linked list takes O(N) time on average.
However, there are some cases where we can find and delete a node in less than O(N) time:
1) When we want to delete the first node of a non-empty linked list, it only requires one step because all that is needed is to adjust the head pointer so it points to second node of the list.
2) When we want to delete the last node of a non-empty linked list, it can be done in two steps: first we find address of previous node (using O(N) time); second we update next pointer of previous node so that it points to NULL (O(1) time).