Consider a singly linked list of the form where F is a pointer to the first…
2018
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
- A.
Delete the last element of the list
- B.
Delete the first element of the list
- C.
Add an element after the last element of the list
- D.
Interchange the first two elements of the list
Attempted by 410 students.
Show answer & explanation
Correct answer: A
In a singly linked list with pointers to both the first (F) and last (L) elements, most operations can be performed in constant time O(1).
Deleting the first element (B) involves updating F, which is O(1). Adding an element after L (C) or swapping the first two elements (D) also only requires pointer updates at known locations, taking O(1).
However, deleting the last element (A) requires finding the node that precedes L. Since it is a singly linked list, we must traverse from F to find the node whose next pointer points to L. This traversal depends on the number of nodes, making it O(n).
Therefore, the time taken for deleting the last element depends on the length of the list.
A video solution is available for this question — log in and enroll to watch it.