Self-organizing doubly linked lists^†

^†Work carried out under Natural Sciences and Engineering Council of Canada. Grants Nos. A-3590 and A-3055.

Abstract

The problem of determining a heuristic which maintains a doubly linked list in approximately optimal order with respect to mean search time is considered. Within a general framework of simple assumptions it is shown that in one particular case no such heuristic can be found, while in many other situations heuristics for similarly maintaining sequential lists should be used. In the remaining circumstances a heuristic known as move to end is shown to reduce search time, on average, to at most twice the minimum value determined by an optimal ordering of the list.

Keywords:

• Doubly linked lists
• searching
• self-organizing heuristics
• move to end

C.R. Categories:

• 3.74
• 4.43
• 5.25

^†Work carried out under Natural Sciences and Engineering Council of Canada. Grants Nos. A-3590 and A-3055.

^†Work carried out under Natural Sciences and Engineering Council of Canada. Grants Nos. A-3590 and A-3055.

Notes

^†Work carried out under Natural Sciences and Engineering Council of Canada. Grants Nos. A-3590 and A-3055.