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?

Question

Computers and Technology

Talan

24 June, 05:37

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?

+2

Answers (1)

Know the Answer?

Justice Mcknight · Answer 1

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).