Double join ordered search

Question

Suppose we have a doubly linked list sorted by an integer value:

struct ListItem { int value; ListItem *prev, *next; }; struct List { ListItem *first, *last; int count; }; 

is it possible to use a faster search algorithm like binary search to find ListItem inside List and how?

Answer 1

For most practical purposes, no. If you need a faster search, a linked list is a poor choice of data structure. Instead, consider a vector, deque, set, or multiset.

Edit: It might be nice to give some idea of ​​which one makes sense when. A vector makes the most sense if you have two fundamentally separate phases: either you insert all of your data into an order, or insert and sort, and then after sorting the data, the data remains static, and you just search in it. Deque is almost the same, except that you can insert from both ends, so if you can get the data out of order, but the new data always refers to one end of the collection or to the other, this can be a good choice.

A set or multiset works better if you are going to mix insert / delete with search. It is constantly sorted, so the search is always fast enough. Between the two (set vs. multiset) the choice is pretty simple: if you want each item in the collection to be unique, you want to set it. If you can have multiple items with the same key, you need a multiset.

Answer 2

If there is no order based on values ​​between nodes, there is no other choice but to check everything individually. Therefore, O (n).

Answer 3

Yes, you can, but if the operation "compare values" is much more expensive than the "pointer movement", it makes absolutely no sense. Since usually “moving” is about as expensive as “comparing” with a normal search:

• O (N) moves
• O (N) comparison

with binary:

• O (N) moves to determine the size of the list
• O (N) moves to find an item
• O (log (N)).

In your example, the value is "int", which means that comparison is even cheaper than movement, so the binary algorithm will be much more expensive.

If you know the size of the list, the binary can (possibly) get cheaper, but the added complexity of 2-way logical movement and counting elements will kill any benefit from reducing the number of value comparisons.

Of course, if you need to search several times, the easiest approach would be to convert the linked list into an array or create an index - an array of pointers. And if the value is something much more complex than int and much more difficult to compare, of course, faster algorithms are most desirable.

Answer 4

Well, you still have to iterate over all the elements to the middle element. I am not sure if binary search will speed up the search through a linked list or not because of this. In the case, for example, your element is in front of the middle element, it would be more logical to logically scroll these elements. Otherwise, you just go to the middle, look where your element is in relation to this, then cycle again and yes ... a bicycle is what really would kill it. I assume that this will also depend on where exactly in the list your item falls.

Answer 5

If you only need to perform a search a couple of times, I suspect that a list search from start to finish will be the best choice. There may be some algorithms that may be more efficient, but it will be slightly better.

If, however, you need to search many times, copying the list into an ordered random-access container that supports binary search will be a transition method.