CODEWITHSUNDEEP
javaalgorithmlinked-listruntimedoubly-linked-list
user3466773
user3466773

Reputation: 186

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)

Upvotes: 2

Views: 19599

Answers (4)

TRUC Vu
TRUC Vu

Reputation: 21

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/

Upvotes: 2

alainlompo
alainlompo

Reputation: 4434

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

Upvotes: 2

user207421
user207421

Reputation: 310884

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.

Upvotes: 6

Joey
Joey

Reputation: 31

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

Upvotes: 1

Related Questions