The Best Search Algorithm for a Linked List

Question

I have to write a program as efficiently as possible that will insert given nodes into a sorted LinkedList. I'm thinking of how binary search is faster than linear in average and worst case, but when I Googled it, the runtime was O(nlogn)? Should I do linear on a singly-LinkedList or binary search on a doubly-LinkedList and why is that one (the one to chose) faster?

Also how is the binary search algorithm > O(logn) for a doubly-LinkedList? (No one recommend SkipList, I think they're against the rules since we have another implementation strictly for that data structure)

Solution 1

You have two choices.

1. Linearly search an unordered list. This is O(N).
2. Linearly search an ordered list. This is also O(N) but it is twice as fast, as on average the item you search for will be in the middle, and you can stop there if it isn't found.

You don't have the choice of binary searching it, as you don't have direct access to elements of a linked list.

But if you consider search to be a rate-determining step, you shouldn't use a linked list at all: you should use a sorted array, a heap, a tree, etc.

Solution 2

Binary search is very fast on arrays simply because it's very fast and simple to access the middle index between any two given indexes of elements in the array. This make it's running time complexity to be O(log n) while taking a constant O(1) space.

For the linked list, it's different, since in order to access the middle element we need to traverse it node by node and therefore finding the middle node could run in an order of O(n)

Thus binary search is slow on linked list and fast on arrays

Solution 3

Binary search is possible by using skip list. You will spend number of pointers as twice as linked list if you set skip 2, 4, 8, ..., 2^n at same time. And then you can get O(log n) for each search.

If your data store in each node is quite big, applying this will very efficient.

You can read more on https://www.geeksforgeeks.org/skip-list/amp/

Solution 4

So basically binary search on a LL is O(n log n) because you would need to traverse the list n times to search the item and then log n times to split the searched set. But this is only true if you are traversing the LL from the beginning every time.

Ideally if you figure out some method (which it's possible!) to start from somewhere else like... the middle of the searched set, then you eliminate the need to always traverse the list n times to start the search and can optimize your algorithm to O(log n).

View more solutions

Comments

[Oliver Charlesworth]

Sure, if you construct a skip list (or equivalent) then O(log n) is possible.

[davmac]

It will be on average twice as fast only for cases where the item is not found.

[Rudy Velthuis]

What tells you that in an unordered list, the item you search for is not, on average near the middle? You stop searching once you found it, right?

[Rudy Velthuis]

Wow, you replied to a comment I made more than 2 years ago. Why wouldn't it be in the middle, on average, if the list is not ordered? I don't see why searching an ordered list sequentially is faster than searching an unordered list sequentially.

[Rudy Velthuis]

I'm not sure if it is O(1). I'd say it is O(log n), which is still fine.

[user207421]

@RudyVelthuis I didn't say it wouldn't be in the middle for an unordered list. I said you can stop in the middle in an ordered list [ if not found, as davmac points out].

[alainlompo]

@RudyVelthuis, thank you: good point, my mistake. Time complexity is O(log n) while space complexity is contant O(1)

[user3466773]

A skiplist is the correct answer in practice, but the problem specifically states that skiplists were against the rules.