原文链接：https://wangwei.one/posts/jav…
前面，我们学习了 链表 的实现，今天我们来学习链表的一个经典的应用场景——LRU 淘汰算法。
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used），本篇将介绍 LRU 策略算法。
LRU Cache
这一算法的核心思想是，当缓存数据达到预设的上限后，会优先淘汰掉近期最少使用的缓存对象。
思路
LRU 淘汰算法涉及数据的添加与删除，出于性能考虑，采用链表来进行实现，思路如下：
维护一个双向链表用于存放缓存数据，越接近链表尾部的数据表示越少被使用到。
放入一个数据时，如果数据已存在则将其移动到链表头部，并更新 Key 所对应的 Value 值，如果不存在，则：
如果缓存容量已达到最大值，则将链表尾部节点删除掉，将新的数据放入链表头部；
如果缓存容量未达到最大值，则直接将新的数据放入链表头部；
查询一个数据时，遍历整个链表，如果能查询到对应的数据，则将其移动到链表头部；如果查询不到则返回 null；
由于遍历链表的时间复杂度为 O(n)，我们可以使用散列表 HashMap 来记录每个 Key 所对应的 Node 节点，将时间复杂度降为 O(1)。
代码
package one.wangwei.algorithms.utils;
import java.util.HashMap;
import java.util.Map;
/**
* LRU Cache
*
* @author https://wangwei.one
* @date 2019/01/29
*/
public class LRUCache<K, V> {
private int capacity;
private Node head;
private Node tail;
private Map<K, Node> nodeMap;
public LRUCache(int capacity) {
this.capacity = capacity;
this.nodeMap = new HashMap<>(capacity);
}
/**
* Get Key
*
* @param key
* @return
*/
public V get(K key) {
Node existNode = nodeMap.get(key);
if (existNode == null) {
return null;
}
remove(existNode);
addFirst(existNode);
return existNode.value;
}
/**
* Add Key-Value
*
* @param key
* @param value
*/
public void put(K key, V value) {
Node existNode = nodeMap.get(key);
if (existNode == null) {
Node newNode = new Node(key, value);
if (nodeMap.size() >= capacity) {
removeLast();
}
addFirst(newNode);
}
else {
// update the value
existNode.value = value;
remove(existNode);
addFirst(existNode);
}
}
/**
* remove node
*
* @param node
*/
private void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
if (prev == null) {
head = next;
} else {
prev.next = next;
}
if (next == null) {
tail = prev;
} else {
next.prev = prev;
}
nodeMap.remove(node.key);
}
/**
* add first node
*
* @param node
*/
private void addFirst(Node node) {
node.prev = null;
if (head == null) {
head = tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
nodeMap.put(node.key, node);
}
/**
* remove last
*/
private void removeLast() {
if (tail == null) {
return;
}
// remove key from map
nodeMap.remove(tail.key);
// remove node from linked list
Node prev = tail.prev;
if (prev != null) {
prev.next = null;
tail = prev;
} else {
head = tail = null;
}
}
private class Node {
private K key;
private V value;
private Node prev;
private Node next;
private Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
源码
LeetCode 上相关的练习题：Leetcode 146. LRU Cache
性能测试：LeetCode 上运行时间为 88ms，超过了 43.42% 的 Java 代码。
相关练习
链表反转
链表环检测
有序链表合并
删除倒数第 N 个节点
求链表的中间结点
参考资料
《数据结构与算法之美》