On Mon, Jan 16, 2012 at 9:48 PM, John Gilmore <[email protected]> wrote:
> Binary search of an ORDERED linked list is in fact possible if one > knows/keeps track of how many elements the list contains. You make me curious, but maybe we're just talking about different things. To me a linked list (ordered or not) is such that you have a pointer to the first element only, and access to any other elements is done by sequentially stepping from the first to the next. When it is ordered, you may know already before the last element that your search will fail. Without further info on the statistics of the data, this would make the failed search be N/2 just like the successful search. An ordered double-linked list could do another half if you're able to hold it in the middle (or at the last item searched, as I've done). Whatever way I look at it, reduction to half or even one fourth is not log(N) except for small numbers. > It may even be be a useful thing to do when pointer-chasing operations > are very much faster than key-comparison operations, as they are in, > say, C. No idea what you refer to. You mean that with large objects it's attractive to keep the head separated (by an extra pointer) from the body so the scanning has a smaller footprint (if someone ensured the heads are placed in another area)? Rob
