缓存比较常见的一种淘汰策略为LRU(Least Recently Used)，即最近最少使用。其实现原理主要包含以下几点：
- HashMap保存Key与缓存节点的映射关系。
- 双向链表(Doubly Linked List)保存缓存节点。
- 被查询节点移动到链表的尾部。
- 当达到缓存最大容量时，移除链表头部节点。
首先实现双向链表节点。
然后实现双向链表。
为何使用双向链表而不是单向链表，因为为保证删除指定节点时可以知道该节点的前置和后置节点，这样才能保证删除节点的时间复杂度为O(1)。从代码可以看出，该链表的新增，弹出和移除节点都达到了O(1)时间复杂度。
最后使用链表和HashMap实现LRU缓存。
保存缓存的HashMap的写入和读取方法以及链表的各方法时间复杂度都为O(1)，所以Cache的写入和读取整体的时间复杂度为O(1)。
测试缓存（最大缓存容量为4）的写入和读取结果如下：
