  The main objective of this survey is to present the important theoretical and
experimental results contributed till date in the area of online algorithms for
the self organizing sequential search problem, also popularly known as the List
Update Problem(LUP) in a chronological way. The survey includes competitiveness
results of deterministic and randomized online algorithms and complexity
results of optimal off line algorithms for the list update problem. We also
present the results associated with list update with look ahead, list update
with locality of reference and other variants of the list update problem. We
investigate research issues, explore scope of future work associated with each
issue so that future researchers can find it useful to work on.

Data Structures and Algorithms