【hot100】146LRU缓存

一、思路

这一题的总体思路并不难想，就是将最近使用的加入/移动到链表头，但是操作较为复杂最好将常用如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)){//若包含，移动到头部，并返回value
                LinkedNode 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);
        }
    }