Least Recently Used
連結リストと連想配列を組み合わせた物を使用すると(例えばJavaのLinkedHashMap)O(1)の時間計算量で計算が可能である。連想配列により、キャッシュからの取り出しはO(1)であり、参照した際に、連結リストの端に持ってくれば良く、これもO(1)である。キャッシュへの挿入も同様にO(1)である。