Speeding Up Search
Finding a specific element in a linked list, even if it is sorted, normally requires O(n) time (linear search). This is one of the primary disadvantages of linked lists over other data structures. In addition to the variants discussed above, below are two simple ways to improve search time.
In an unordered list, one simple heuristic for decreasing average search time is the move-to-front heuristic, which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.
Another common approach is to "index" a linked list using a more efficient external data structure. For example, one can build a red-black tree or hash table whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).
Read more about this topic: Linked List
Famous quotes containing the words speeding up, speeding and/or search:
“The correct rate of speed in innovating changes in long-standing social customs has not yet been determined by even the most expert of the experts. Personally I am beginning to think there is more danger in lagging than in speeding up cultural change to keep pace with mechanical change.”
—Mary Barnett Gilson (1877–?)
“At death, you break up: the bits that were you
Start speeding away from each other for ever
With no one to see.”
—Philip Larkin (1922–1986)
“why
Do our black faces search the empty sky?
Is there something we have forgotten? some precious thing
We have lost, wandering in strange lands?”
—Arna Bontemps (1902–1973)