摘要：
1，LRU的介绍
2，LRU元素的添加
3，LRU元素的读取
4，LRU完整代码实现
1，LRU的介绍
LRU(Least Recently Used)最近最少使用，它是一种缓存淘汰策略。也就是说在缓存容量满的时候，我们需要删除一些元素，删除的原则就是越久没被使用的越容易被删除。
举个简单例子，比如你桌子上的书堆满了，需要拿掉一部分，你肯定是优先拿掉那些很久没有看的书，经常看的书肯定会优先留下来。
LRU要做的就是根据元素使用的时间来保持它们的顺序，维持相对顺序的数据结构使用的是双向链表。
如下图所示，最近被使用的元素会靠近链表头部，越久没被使用的元素越靠近尾部，删除的时候优先删除离尾部最近的元素，其中链表的头节点 head 和尾节点 tail 是不存储任何数据的。
我们先来看下链表的节点类，不熟悉双向链表的可以先看下前面讲的《双向链表》。
Java 代码：
// 双向链表的节点类
class LinkedNode {int key, val;// 节点的key和val值LinkedNode pre;// 指向前一个节点的指针LinkedNode next;// 指向后一个节点的指针
}C++ 代码：
// 双向链表的节点类
struct LinkedNode {int key, val;// 节点的key和val值LinkedNode *pre = nullptr;// 指向前一个节点的指针LinkedNode *next = nullptr;// 指向后一个节点的指针
};2，LRU元素的添加
LRU中的元素是根据键值对存储在map中的，关于map的知识点可以看下前面的《散列表》，双向链表只是维护元素使用的时间顺序。
在添加的时候如果 key 值已经存在了，我们直接更新value值，更新完之后要把它重新插入到链表的前面，如下图所示。
添加的时候如果 key 值不存在，直接插入到链表的前面，如下图所示。
