（链表）19-LRU缓存

  1 public class LRUCache {
  2 
  3     // 双向链表节点的构造函数
  4     class DLinkedNode {
  5         // 双向链表-Key
  6         int key;
  7         // 双向链表-Val
  8         int value;
  9         // 双向链表-前指针
 10         DLinkedNode pre;
 11         // 双向链表-后指针
 12         DLinkedNode next;
 13         // 构造函数-空参数
 14         public DLinkedNode() {
 15         }
 16         // 构造函数-完全参数
 17         public DLinkedNode(int inputKey, int inputVal) {
 18             key = inputKey; 
 19             value = inputVal;
 20         }
 21     }
 22 
 23     // 哈希表
 24     private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
 25     // LRU缓存-已填充的数据量
 26     private int size;
 27     // LRU缓存-容量
 28     private int capacity;
 29     // 伪头结点
 30     private DLinkedNode head;
 31     // 伪尾结点
 32     private DLinkedNode tail;
 33 
 34     // LRU缓存构造函数
 35     public LRUCache(int capacity) {
 36         this.size = 0;
 37         this.capacity = capacity;
 38         // 添加伪头部和伪尾部节点
 39         head = new DLinkedNode();
 40         tail = new DLinkedNode();
 41         head.next = tail;
 42         tail.pre = head;
 43     }
 44 
 45     public int get(int key) {
 46         DLinkedNode node = cache.get(key);
 47         // KEY不存在返回-1
 48         if (node == null) {
 49             return -1;
 50         }
 51         // 如果KEY存在-先通过哈希表定位-再移到头部
 52         moveToHead(node);
 53         // 返回KEY对应节点值
 54         return node.value;
 55     }
 56 
 57     public void put(int key, int value) {
 58         DLinkedNode node = cache.get(key);
 59         if (node == null) {
 60             // KEY不存在-创建一个新的节点
 61             DLinkedNode newNode = new DLinkedNode(key, value);
 62             // 添加进哈希表
 63             cache.put(key, newNode);
 64             // 添加至双向链表的头部
 65             addToHead(newNode);
 66             // 数据量+1
 67             size ++;
 68             if (size > capacity) {
 69                 // 超出容量，删除双向链表的尾部节点
 70                 DLinkedNode tail = removeTail();
 71                 // 删除哈希表中对应的项
 72                 cache.remove(tail.key);
 73                 // 数据量-1
 74                 size --;
 75             }
 76         } else {
 77             // KEY存在-先通过哈希表定位修改VAL
 78             node.value = value;
 79             // 将刚刚使用的节点移到头部
 80             moveToHead(node);
 81         }
 82     }
 83 
 84     // 将入参节点添加到头结点
 85     private void addToHead(DLinkedNode node) {
 86         node.pre = head;
 87         node.next = head.next;
 88         head.next.pre = node;
 89         head.next = node;
 90     }
 91 
 92     // 删除入参节点
 93     private void removeNode(DLinkedNode node) {
 94         node.pre.next = node.next;
 95         node.next.pre = node.pre;
 96     }
 97 
 98     // 将入参节点移动到链表最前面
 99     private void moveToHead(DLinkedNode node) {
100         removeNode(node);
101         addToHead(node);
102     }
103 
104     // 移除尾部结点-返回移除的节点
105     private DLinkedNode removeTail() {
106         DLinkedNode res = tail.pre;
107         removeNode(res);
108         return res;
109     }
110 }