一、思路
这一题的总体思路并不难想，就是将最近使用的加入/移动到链表头，但是操作较为复杂最好将常用如addhead(),removetail()等函数单独抽成可供重复使用的函数，这样显著增加了代码可读性和简洁性
二、记忆
1.双向链表的操作，头尾哑结点的使用
2.由于链表的查找性能很弱，每次查找都要遍历，所以我们使用HashMap来加速擦找流程
三、代码
public class LRUCache {class LinkedNode{//双向链表类int key;int value;LinkedNode prev;LinkedNode next;public LinkedNode(){};/*默认构造方法，它会创建一个 LinkedNode 对象，但是不会对任何字段进行初始化。如果没有特别的初始化需求，可以使用这个构造方法来创建一个空的节点实例。默认值：int 类型的 key 和 value 会被初始化为 0。LinkedNode 类型的 prev 和 next 会被初始化为 null。*/public LinkedNode(int key,int value){this.key = key;this.value = value;}}private Integer capacity;private Integer length = 0;//存储链表长度HashMap<Integer,LinkedNode> listNodeHashMap = new HashMap<>();//查找属性是否存在private LinkedNode head ;private LinkedNode tail ;public LRUCache(int capacity) {this.capacity= capacity;head = new LinkedNode();tail = new LinkedNode();}public int get(int key) {if(listNodeHashMap.containsKey(key)){//若包含，移动到头部，并返回valueLinkedNode temp = listNodeHashMap.get(key);remove(temp);addhead(key,temp.value);return listNodeHashMap.get(key).value;}else {return -1;}}public void put(int key, int value) {if (listNodeHashMap.isEmpty()){LinkedNode temp = new LinkedNode(key,value);head.next = temp;temp.prev = head;temp.next = tail;tail.prev = temp;length++;listNodeHashMap.put(key,temp);}else if ( listNodeHashMap.containsKey(key)){//若包含，则将节点移动到头结点LinkedNode temp = listNodeHashMap.get(key);temp.value = value;remove(temp);addhead(key,value);}else if(length<capacity){//若不包含且未满，将节点添加到头结点addhead(key,value);length++;}else {//若不包含且已满，则删除尾节点，将新节点添加到头结点removetail();addhead(key,value);}}private void addhead(int key,int value){//将节点添加到哑头结点之后LinkedNode temp = new LinkedNode(key,value);temp.next = head.next;temp.next.prev = temp;head.next = temp;temp.prev = head;listNodeHashMap.put(key,temp);}private void removetail(){//将尾节点移除LinkedNode temp = tail.prev ;tail.prev = temp.prev;temp.prev.next = tail;listNodeHashMap.remove(temp.key);}private void remove(LinkedNode temp){//将节点移除temp.prev.next = temp.next;temp.next.prev = temp.prev;listNodeHashMap.remove(temp.key);}}
