力扣_146_LRU 缓存_java

代码不是很好，粗糙的实现了，有空回来补改

用map存储键值对，值使用双链表存储

class LRUCache {
    int size=0;
    static class node{
        int key,val;

        node(int key,int i){
            val=i;
            this.key=key;

        }
        node(){
        }
        node left,right;
    }
    node head=new node();
    node tail=new node();
    int capacity;
    HashMap<Integer,node> map=new HashMap<>();
    public LRUCache(int capacity) {
        this.capacity=capacity;
                    head.right=tail;
            tail.left=head;
    }
    
    public int get(int key) {
        node cur=map.getOrDefault(key,null);
        if(cur!=null){
            cur.left.right=cur.right;
            cur.right.left=cur.left;
            
            cur.left=tail.left;
            tail.left.right=cur;
            cur.right=tail;
            tail.left=cur;
            return cur.val;
        }
        
        return -1;
    }
    
    public void put(int key, int value) {
        node isexist=map.getOrDefault(key,null);
        if(isexist!=null){
            isexist.val=value;
        isexist.left.right=isexist.right;
        isexist.right.left=isexist.left;

        isexist.left=tail.left;
        isexist.right=tail;
        tail.left.right=isexist;
        tail.left=isexist;
        }
        else{
        node n=new node(key,value);
        map.put(key,n);
        n.left=tail.left;
        n.right=tail;
        tail.left.right=n;
        tail.left=n;
                if(capacity>0)capacity--;
        else {
            map.remove(head.right.key);
            head.right=head.right.right;
            head.right.left=head;
    }
    }

}}