The Best Search Algorithm for a Linked List

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)