Static Ordering

Recall: Unordered list/array implementation of ADT Dictionary search: Θ(n), insert: Θ(1), delete: Θ(1) (after a search)

Lists/arrays are a very simple and popular implementation. Can we do something to make search more effective in practice?

No: if items are accessed equally likely
Yes: otherwise (we have a probability distribution of the items) ▶  Intuition: Frequently accessed items should be in the front. ▶  Two cases: Do we know the access distribution beforehand or not? ▶  For short lists or extremely unbalanced distributions this may be faster than AVL trees or Skip Lists, and much easier to implement.