LRU缓存机制实现

class LRUCache{
    class Node{
        Node next,pre;
        int val,key;//这个很关键，必须要有key，这样在删除的时候才能反向找到map的key
        public Node(int key, int val){
            pre = null;
            next = null;
            this.val = val;
            this.key = key;
        }
    }
    int MAX_LEN;
    Map<Integer, Node> map = new HashMap<>();
    Node head = new Node(0,0);
    public LRUCache(int k){
        head.pre = head;
        head.next = head;
        MAX_LEN = k;
    }
    public void put(int key, int value){
        if(map.containsKey(key)) {
            Node p = map.get(key);
            update(p);
            p.val = value;
        }else {
            if(map.size() == MAX_LEN) {
                map.remove(head.pre.key);
                delete(head.pre);
            }
            map.put(key, insertFirst(new Node(key, value)));
        }
    }
    public int get(int k){
        int res = -1;
        if(map.containsKey(k)) {
            Node p = map.get(k);
            update(p);
            res = p.val;
        }
        return res;
    }
    public void delete(Node p) {
        p.next.pre = p.pre;
        p.pre.next = p.next;
    }
    public Node insertFirst(Node p) {
        p.next = head.next;
        p.pre = head;
        head.next.pre = p;
        head.next = p;
        return p;
    }
    public void update(Node p) {
        delete(p);
        insertFirst(p);
    }
}