This article studies the amortized efficiency of the "move-to-front" rule and similar heuristics for maintaining a linear list. Under the assumption that accessing the $i$th element from the front of the list takes $\Theta(i)$ time, the authors show that the move-to-front rule is within a constant factor of optimum among a wide class of list maintenance rules. Other heuristics, such as the transpose and frequency count rules, do not share this property. The results are generalized to show that the move-to-front rule is approximately optimal as long as the access cost is a convex function. In the context of paging, where the access cost is not convex, the authors analyze the "least recently used" (LRU) replacement rule. They show that its amortized complexity differs from the offline paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory, and no online paging algorithm has better amortized performance. The article provides theoretical support for the practical observations that move-to-front is often the best rule in real-world applications.This article studies the amortized efficiency of the "move-to-front" rule and similar heuristics for maintaining a linear list. Under the assumption that accessing the $i$th element from the front of the list takes $\Theta(i)$ time, the authors show that the move-to-front rule is within a constant factor of optimum among a wide class of list maintenance rules. Other heuristics, such as the transpose and frequency count rules, do not share this property. The results are generalized to show that the move-to-front rule is approximately optimal as long as the access cost is a convex function. In the context of paging, where the access cost is not convex, the authors analyze the "least recently used" (LRU) replacement rule. They show that its amortized complexity differs from the offline paging rule (Belady's MIN algorithm) by a factor that depends on the size of fast memory, and no online paging algorithm has better amortized performance. The article provides theoretical support for the practical observations that move-to-front is often the best rule in real-world applications.