CODEWITHSUNDEEP
algorithmdata-structuresdictionary
test123
test123

Reputation: 41

Question regarding Algorithm Design Manual - Data Structure for the Dictionary

I started reading Algorithm Design Manual, and while reading it I came across one line which I am not getting. Can someone please clarify me what does author mean here? The line is:

Sorted linked lists or arrays – Maintaining a sorted linked list is usually not worth the effort unless you are trying to eliminate duplicates, since we cannot perform binary searches in such a data structure. A sorted array will be appropriate if and only if there are not many insertions or deletions.

This line is in context with choosing data structure for dictionary. The point that I am not getting is, why does author says that "Maintaining a sorted linked list is usuallynot worth the effort unless you are trying to eliminate duplicates, since we cannot perform binary searches in such a data structure"

From what I understood I googled to see if we can binary search on sorted arrays and based on what I found it looks like we can. So I am not sure.

Can someone please help me understand this?

Thanks so much.

Upvotes: 2

Views: 477

Answers (1)

Karel Petranek
Karel Petranek

Reputation: 15164

You cannot perform binary search on linked list efficiently because you cannot randomly seek in it in constant time. To find the midpoint you have to do n/2 steps (traverse the list). This adds a great overhead and makes lists unsuitable for binary search data structures.

Upvotes: 5

Related Questions