On linear search heuristics (Q1114411)

Linear search is an extensively used example in association with self- adjusting data structures. The most common restructuring rules for unsorted linear lists, the move- to-front rule and the transpose rule, are compared with another one, the rotation rule. If the lists are implemented by using records and pointers or in the case when arrays are used, the implementation of rotation is more efficient then the corresponding move-to-front implementation.