注意区分这里的LinkedHashMap不是把HashMap中的每个桶下的链表变成双向链表而是一条单独的全局双向链表定义双向链表节点class DLinkedNode{ int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode(){} public DLinkedNode(int kkey,int vvalue){key kkey;value vvalue;} }LRU内部构造定义private MapInteger, DLinkedNode cache new HashMapInteger, DLinkedNode(); private int size; private int capacity; private DLinkedNode head, tail;构造方法public LRUCache(int capacity) { this.size 0; this.capacity capacity; // 使用伪头部和伪尾部节点 head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; }小贴士在双向链表的实现中使用一个伪头部dummy head和伪尾部dummy tail标记界限这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。get方法public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; } // 如果 key 存在先通过哈希表定位再移到头部 moveToHead(node); return node.value; }put方法public void put(int key, int value) { DLinkedNode node cache.get(key); if (node null) { // 如果 key 不存在创建一个新的节点 DLinkedNode newNode new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); size; if (size capacity) { // 如果超出容量删除双向链表的尾部节点 DLinkedNode tail removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } }注意添加到链表不代表已经添加到hashmap里了都要加看完整代码public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() {} public DLinkedNode(int _key, int _value) {key _key; value _value;} } private MapInteger, DLinkedNode cache new HashMapInteger, DLinkedNode(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size 0; this.capacity capacity; // 使用伪头部和伪尾部节点 head new DLinkedNode(); tail new DLinkedNode(); head.next tail; tail.prev head; } public int get(int key) { DLinkedNode node cache.get(key); if (node null) { return -1; } // 如果 key 存在先通过哈希表定位再移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node cache.get(key); if (node null) { // 如果 key 不存在创建一个新的节点 DLinkedNode newNode new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); size; if (size capacity) { // 如果超出容量删除双向链表的尾部节点 DLinkedNode tail removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } } else { // 如果 key 存在先通过哈希表定位再修改 value并移到头部 node.value value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } private void removeNode(DLinkedNode node) { node.prev.next node.next; node.next.prev node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res tail.prev; removeNode(res); return res; } }