题目描述（中等难度）

缓存。存储空间有限，当存满的时候的一种淘汰策略。LRU 选择删除最远一次操作过的元素，操作包括get 或者 put 。换句话讲，最开始 put 进去的如果没有进行过 ，那存满的时候就先删它。

思路分析

看到 O(1) 的时间复杂度首先想到的就是用 HashMap 去存储。

之后的问题就是怎么实现，当存满的时候删除最远一次操作过的元素。

可以用一个链表，每 put 一个 元素，就把它加到链表尾部。如果 get 某个元素，就把这个元素移动到链表尾部。当存满的时候，就把链表头的元素删除。

接下来还有一个问题就是，移动某个元素的时候，我们可以通过 直接得到这个元素，但对于链表，如果想移动一个元素，肯定需要知道它的前一个节点才能操作。

而找到前一个元素，最直接的方法就是遍历一遍，但是这就使得算法的时间复杂度就不再是 O(1) 了。

综上，HashMap 加上双向链表即可解这道题了。

解法一

有了上边的思路，接下来就是实现上的细节了，最后的参考图如下。

首先定义节点。

定义双向链表类。

这里用了一个 dummyHead ，也就是哨兵节点，不存数据，可以把链表头结点等效于其他的节点，从而简化一些操作。

接下来把上边的代码放在一起就可以了。

总

最关键的其实就是双向链表的应用了，想到这个点其他的话就水到渠成了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情