Question

Suppose you are give a linked list of integers whose items are sorted. Which is the most efficient way to search the list to determine if a given value x is in the list?

Answer 1

Answer:

Linear Search.

Explanation:

Binary search is an efficient method for the arrays because in arrays accessing the middle element is very easy and fast but accessing middle in linked is not as easy as arrays the memory allocation of nodes of linked list is dynamic.

So to find an element with value x in the linked list we can search it by traversing the list.Visiting each node at a time.

Whose worst case time complexity will be O(n).