缓存LRU算法(哈希链表)

public class LRUCache{
    
    private HashMap<Integer,Node> map;
    
    private DoubleList cache;
    
    //capacity
    private int cap;
    
    public LRUCache(int capacity){
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key){
        if(!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
        put(key,val);
        return val;
    }
    
    public void put(int key,int val){
        Node x = new Node(key,val);
        
        if(map.containsKey(key)){
            //更新位置
            cache.remove(map.get(key));
            cache.addFirst(x);
            map.put(key,x);
        }else{
            if(cap == cache.size()){
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            
            cache.addFirst(x);
            map.put(key,x);
        }
    }
}

class Node{
    public int key,val;
    public Node next,prev;
    public Node(int k,int v){
        this.key = k;
        this.val = v;
    }
}

class DoubleList{
    
    public void addFirst(Node x);
    
    public void remove(Node x);
    
    public Node removeLast();
}