We consider the problem of adaptively organizing a list whose elements are accessed with a fixed but unknown probability distribution. We present an absorbing scheme requiring constant additional space which reorganizes the list by performing a restructuring operation on an element exactly once. The scheme is asymptotically optimal. We also describe a hybrid reorganization scheme in which the absorbing rule and an ergodic rule are used in conjunction with each other to enhance the transient data retrieval process.

Additional Metadata
Persistent URL dx.doi.org/10.1016/0304-3975(93)90166-Q
Journal Theoretical Computer Science
Citation
Oommen, J, & Ng, D.T.H. (David T.H.). (1993). An optimal absorbing list organization strategy with constant memory requirements. Theoretical Computer Science, 119(2), 355–361. doi:10.1016/0304-3975(93)90166-Q