title: The Best Search Algorithm for a Linked List
body: <p>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?</p>
  
  <p>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)</p>