The class of memoryless heuristics for maintaining a Doubly-Linked List in an approximately optimal order is studied. Two mappings that relate Singly-Linked List and Doubly-Linked List heuristics are defined, and theorems involving these mappings are presented. A new heuristic referred to as the Swap heuristic for the Doubly-Linked List is introduced, and its asymptotic distribution has been derived.

Additional Metadata
Persistent URL dx.doi.org/10.1093/comjnl/35.5.533
Journal Computer Journal
Citation
Ng, D.T.H. (D. T H), & Oommen, J. (1992). A short note on doubly-linked list reorganizing heuristics. Computer Journal, 35(5), 533–535. doi:10.1093/comjnl/35.5.533