简单实现LRUCache

　　前几天，录了一个实现LRUCache的视频，但是并没有说明为什么是这样设计的，所以本文将分享一下设计的思路。LRU的基本概念：
　　LRU是Least Recently Used的缩写，最近最少使用算法。 LRU的查询、添加、删除、修改的时间复杂度O(1)：
　　使用哈希表快速定位到对应的节点上，然后通过简单的指针变换进行元素的增删改查LRU的Java实现：哈希表 + 双向链表
　　1、定义双向链表Node节点class Node {         int key;         int value;         Node prev;         Node next;          public Node() {         }          public Node(int key, int value) {             this.key = key;             this.value = value;         }          @Override         public String toString() {             return ＂Node{＂ +                     ＂key=＂ + key +                     ＂, value=＂ + value +                     ＂}＂;         }     }
　　2、定义LRUCache的相关属性//当前LRUCache的数量 private int size; //LRUCache的容量 private int capacity; //双向链表的头结点 private Node head; //双向链表的尾结点 private Node tail; //哈希表 key: key， value: 双向链表的节点 private Map cache = new HashMap<>();
　　3、初始化LRUCache public LRUCache(int capacity) {         this.capacity = capacity;         this.size = 0;         this.head = new Node();         this.tail = new Node();         this.head.next = tail;         this.tail.prev = head;     }
　　4、定义几个常用的方法
　　删除节点：private void removeNode(Node node) {     node.next.prev = node.prev;     node.prev.next = node.next; }
　　将节点添加到头结点：private void addToHead(Node node) {     node.next = head.next;     head.next.prev = node;     node.prev = head;     head.next = node; }
　　将节点移动到头结点：private void moveToHead(Node node) {     removeNode(node);     addToHead(node); }
　　5、定义LRUCache的添加、修改和查询
　　查询：public int get(int key) {     Node node = cache.get(key);     if (node == null) {         return -1;     }     moveToHead(node);     return node.value; }
　　添加和修改：public void put(int key, int value) {     Node node = cache.get(key);     if (node == null) {         Node newNode = new Node(key, value);         cache.put(key, newNode);         addToHead(newNode);         size++;         if (size > capacity) {             removeNode(tail.prev);             size--;         }     } else {         node.value = value;         moveToHead(node);     } }
　　6、打印LRUCachepublic void print() {     System.out.println(＂-------------------------------------------------------------------------＂);     Node cur = head.next;     while (cur.next != null) {         System.out.println(＂prev: ＂ + cur.prev + ＂, cur: ＂ + cur + ＂, next: ＂ + cur.next);         cur = cur.next;     } }
　　7、测试public static void main(String[] args) {     LRUCache cache = new LRUCache(5);     cache.put(1, 10);     cache.put(2, 20);     cache.put(3, 30);     cache.put(4, 40);     cache.put(5, 50);     cache.put(6, 60);     cache.print();     System.out.println(cache.get(4));     cache.print();     cache.put(6, 999);     cache.print(); }
　　8、结果------------------------------------------------------------------------- prev: Node{key=0, value=0}, cur: Node{key=6, value=60}, next: Node{key=5, value=50} prev: Node{key=6, value=60}, cur: Node{key=5, value=50}, next: Node{key=4, value=40} prev: Node{key=5, value=50}, cur: Node{key=4, value=40}, next: Node{key=3, value=30} prev: Node{key=4, value=40}, cur: Node{key=3, value=30}, next: Node{key=2, value=20} prev: Node{key=3, value=30}, cur: Node{key=2, value=20}, next: Node{key=0, value=0} 40 ------------------------------------------------------------------------- prev: Node{key=0, value=0}, cur: Node{key=4, value=40}, next: Node{key=6, value=60} prev: Node{key=4, value=40}, cur: Node{key=6, value=60}, next: Node{key=5, value=50} prev: Node{key=6, value=60}, cur: Node{key=5, value=50}, next: Node{key=3, value=30} prev: Node{key=5, value=50}, cur: Node{key=3, value=30}, next: Node{key=2, value=20} prev: Node{key=3, value=30}, cur: Node{key=2, value=20}, next: Node{key=0, value=0} ------------------------------------------------------------------------- prev: Node{key=0, value=0}, cur: Node{key=6, value=999}, next: Node{key=4, value=40} prev: Node{key=6, value=999}, cur: Node{key=4, value=40}, next: Node{key=5, value=50} prev: Node{key=4, value=40}, cur: Node{key=5, value=50}, next: Node{key=3, value=30} prev: Node{key=5, value=50}, cur: Node{key=3, value=30}, next: Node{key=2, value=20} prev: Node{key=3, value=30}, cur: Node{key=2, value=20}, next: Node{key=0, value=0}
　　如果有什么问题，或者有什么错误，欢迎评论区提出，谢谢各位大大