In the worst case, the number of comparisons needed to search a singly linked…
2002
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is:
- A.
log₂ n
- B.
n/2
- C.
log₂ n - 1
- D.
n
Attempted by 102 students.
Show answer & explanation
Correct answer: D
A singly linked list must be searched sequentially from the head because it has no direct indexing. In the worst case, the required element is either at the last node or not present in the list. Therefore, every one of the n nodes must be compared once. Hence the worst-case number of comparisons is n.