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)

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