思路

代码

  class LRUCache {//初始化节点：key+value+pre+nextclass Node {int key;int value;Node next;Node prev;public Node(int key, int value) {this.key = key;this.value = value;}}//设置链表需要的属性//最大容量int capacity=0;//当前长度int size=0;//头节点Node head;//尾节点//!!尾节点也要弄使用那种空节点Node rear;//初始化链表，本质就是对链表的属性 进行一些初始的设置public LRUCache(int capacity){this.capacity=capacity;//使用-1作为区分head=new Node(-1, -1);rear=new Node(-2, -2);rear.prev=head;head.next=rear;}/*** 根据key寻找节点，如果存在，返回节点* 如果不存在，返回null* @param key 需要找的节点的key* @return 返回整个节点node*/public Node getNode(int key){//判断是否当前节点的key等于 "参数key"Node cur=head.next;while(cur!=null){if (cur.key==key){return cur;}cur=cur.next;}//全部遍历后，还没有返回，说明没有这个节点，所以返回nullreturn null;}/*** 根据key寻找节点，并返回value，* 如果存在这个节点，返回value* 如果不存在，返回-1* 同时注意：使用这个方法以后，需要把这个节点放到头部* @param key* @return*/public int get(int key){Node node = getNode(key);if (node==null){return -1;}//没有返回，说明存在这个节点，则返回节点的value//同时做最近使用处理hadUsed(node);return node.value;}/*** 如果key存在，更改这个value* 如果不存在，先头增，再判断是否需要尾删* @param key* @param value*/public void put(int key, int value){Node nodeGet = getNode(key);//如果存在if (nodeGet!=null){nodeGet.value=value;hadUsed(nodeGet);}//如果不存在else {Node nodeAdd = new Node(key, value);//头增,并size++,,如果这个put是第一次，那么，rear就要向后走addFirst(nodeAdd);size++;//判断是否尾删if (size>capacity){removeLast();}}}//头增，并判断是不是第一次public boolean addFirst(Node node){node.next=head.next;node.prev=head;node.next.prev=node;head.next=node;return true;}//尾删：public boolean removeLast(){Node nodeToRemove=rear.prev;removeByNode(nodeToRemove);return true;}//把当前节点，在链表中删除private void removeByNode(Node node) {//最好 4个操作都写好//删除需要 解除这个节点和链表的联系，所以pre和next都要赋空值node.prev.next=node.next;node.next.prev=node.prev;node.next=null;node.prev=null;}public void hadUsed(Node node){removeByNode(node);addFirst(node);}}

记录

总结

尾删是一种 特殊的  删除某个元素

所以可以直接调用：删除某个元素