On the list update problem
Christoph Ambühl · Repository for Publications and Research Data (ETH Zurich) · 2002
An unsorted linear list is one of the simplest data structures on which one can perform insertions, deletions and lookups.To perform a lookup, the list has to be traversed linearly until the requested item is found.The performance of this data structure can be enhanced by making it self-organizing.In general, the most recently requested item will be moved closer to the front of the list.This is motivated by the empirical observation that, in many cases, requests to items are clustered over time.