ordered doubly linked list search

suppose we have doubly linked list ordered by integer value:

struct ListItem
{
  int value;
  List开发者_运维知识库Item *prev, *next;
};

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

can we use faster search algorithm such as binary search to locate ListItem inside List and how?

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

Edit: Perhaps it would be good to provide some guidance about which of those makes sense when. A vector makes the most sense if you have two basically separate phases: Either you insert all your data in order, or you insert and sort, then after the data is sorted, the data remains static, and you just search in it. A deque is pretty much the same, except you can insert at either end, so if you might get data out of order, but new data always belongs at one end of the collection or the other, it can be a good choice.

A set or multiset works better if you're going to be mixing insertions/deletions with lookups. It stays sorted all the time, so searches are always reasonably fast. Between the two (set vs. multiset) the choice is pretty simple: if you need to ensure each item in the collection is unique, you want set. If you might have more than one item with the same key, you want a multiset.

If there is no ordering among the nodes based on there values, no other choice remains but to check all individually. Hence O(n).

Yes, you can, but unless operation of "compare values" is far costlier than "move pointer" it makes entirely no sense. Since usually "move" is about as costly as "compare", with plain search:

• O(N) moves
• O(N) comparisons

with binary:

• O(N) moves to determine size of the list
• O(N) moves to locate the element
• O(log(N)) comparisons.

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

If you know the size of the list, binary might (arguably) get cheaper, but the added complexity of 2-directional logic travel and element-counting will kill any benefit from reduced number of value comparisons.

Of course if you need to search multiple times, the easiest approach will be to transform the linked list into an array or create an index - an array of pointers. And in case the value is something far more sophisticated than int and much more difficult to compare, of course the faster algorithms will be most desired.

Well, you'll still have to cycle through all the elements up to the middle element. I'm not really sure if the binary search would speed up the search through a linked list or not because of this. In the case for example, your element is before the middle element, it would seem faster logically to just cycle through those elements. Otherwise, you're just going to go to the middle, see where your element is in relation to that, then cycle again and yea...the cycling is what would really kill this. I guess it would also depend on exactly where in the list your element falls.

If you only have to perform the search for a couple of times, I suspect searching through the list from start to end would be the best choice. There may be some algorithms that can be more efficient, but it would only be slightly better.

If, however, you have to perform the search for many times, copying the list into an ordered, random-access container that support binary search would be the way to go.