解決什么問題

為了提高效率，很多數據是可以放在內存中的，但是內存空間是有限的，假如數據滿了，再添加數據，應該清除哪些數據了。LRU就是一種清除數據的策略，LRU是Least Recently Used的縮寫，即最近最少使用的數據可以清除

數據結構

我們使用HashMap來存放數據，再使用雙向鏈表來維護最近最少使用的順序，雙向鏈表從頭到尾依次最近最少使用的到最近最多使用的

上圖中，依次加入A，B，C這時候訪問一下A，則把A放在鏈表的尾部

如果空間只夠存儲3個元素，這時候要加D了，就需要頭部的B彈出，把D放在尾部。

所以，每次訪問的元素或者添加的元素就放在隊尾，也就是最近最常用的元素，那么放在頭部的就是最近最少使用的元素。

代碼

JAVA中的LinkedHashMap其實就是這樣一個結構，Map中這幾個方法沒有實現，LinkedHashMap實現了。

可以使用HashMap和鏈表來實現，下面的代碼是鏈表中的幾個關鍵步驟：

定義數據結構（節點，雙向鏈表，一個頭，一個尾）：

添加節點操作

容量滿了刪除最近最少使用的

每次訪問都把元素放在尾部