From Wikipedia, the free encyclopedia

A self-organizing list is a list that reorders its elements based on some self-organizing heuristic to improve average access time.

Some say, the "Self Organizing List" is a poor man's Hash table (see Gwydion Dylan Library Reference Guide). By using a probabilistic strategy, it yields nearly constant time in the best case for insert/delete operations, although the worst case remains linear.

[edit] References

• NIST DADS entry

there are four ways in which the list can be self organized: 1. ordering 2. transpose 3. move to front 4. count