解决什么问题

为了提高效率，很多数据是可以放在内存中的，但是内存空间是有限的，假如数据满了，再添加数据，应该清除哪些数据了。LRU就是一种清除数据的策略，LRU是Least Recently Used的缩写，即最近最少使用的数据可以清除

数据结构

我们使用HashMap来存放数据，再使用双向链表来维护最近最少使用的顺序，双向链表从头到尾依次最近最少使用的到最近最多使用的

上图中，依次加入A，B，C这时候访问一下A，则把A放在链表的尾部

如果空间只够存储3个元素，这时候要加D了，就需要头部的B弹出，把D放在尾部。

所以，每次访问的元素或者添加的元素就放在队尾，也就是最近最常用的元素，那么放在头部的就是最近最少使用的元素。

代码

JAVA中的LinkedHashMap其实就是这样一个结构，Map中这几个方法没有实现，LinkedHashMap实现了。

可以使用HashMap和链表来实现，下面的代码是链表中的几个关键步骤：

定义数据结构（节点，双向链表，一个头，一个尾）：

添加节点操作

容量满了删除最近最少使用的

每次访问都把元素放在尾部