Data Structures | Linked List | Question 9
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is [GATE CS 2002]
[A] log 2 n
[B] n/2
[C] log 2 n – 1
[D] n
Answer: [D]
Explanation: In the worst case, the element to be searched has to be compared with all elements of linked list.
Quiz of this Question
GATE | GATE-CS-2002 | Question 5
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
[A] log2 n
[B] n/2
[C] log2n – 1
[D] n
Answer: [D]
Explanation: Singly linked list has uni – directional flow, i.e., it has only one pointer for moving [the next pointer].
In the worst case, for searching an element in the singly linked list, we will have to traverse the whole list [the case when the required element is either the last element or is not present in the list].
So, in the worst case for a list of length n, we will have to go to each node for comparison and thus, we would be needing ‘n’ comparisons.
Thus, D is the correct choice.
Please comment below if you find anything wrong in the above post.
Quiz of this Question