Question

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) log2 n – 1

(d) n

The above asked question is from Singly Linked List Operations topic in portion Abstract Data Types of Data Structures & Algorithms I

The question was asked in quiz.

Answer 1

Correct answer is (d) n

The best I can explain: The worst-case happens if the required element is at last or the element is absent in the list. For this, we need to compare every element in the linked list. If n elements are there, n comparisons will happen in the worst case.