Move-to-end is best for double-linked lists
Vladimir Estivill‐Castro · 2003
The authors demonstrate that Move-to-End (ME) is statically competitive for doubly linked lists. That is, ME is competitive with respect to the class of off-line static heuristics for doubly-linked lists. ME is competitive with respect to the class of on-line dynamic heuristics that use, per query, one end of the doubly-linked list. Moreover, other heuristics, like Swap do not have these properties. Since one can prove that there is no competitive heuristic for the class of on-line dynamic memoryless deterministic heuristics, ME offers the best competitiveness behavior.>