146. LRU 缓存机制

 
 class Node{
    //Node属性有 key val  前驱节点  后继节点
    int key,val;
    Node prev,next;
    public Node(int key,int val){
        this.key=key;
        this.val=val;
    }
}
 
 

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

    private Node head, tail;
    private int size;

    public void addFirst(Node node) {
        if (head == null) {
            head = tail = node;
        } else {
            Node n = head;
            n.prev = node;
            node.next = n;
            head = node;
        }
        size++;
    }

    public void remove(Node node) {
        if (head == node && tail == node) {
            head = null;
            tail = null;
        } else if (tail == node) {
            node.prev.next = null;
            tail = node.prev;
        } else if (head == node) {
            node.next.prev = null;
            head = node.next;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        size--;
    }

    public Node removeLast() {
        Node node = tail;
        remove(tail);
        return node;
    }

    public int size() {
        return size;
    }
}

private HashMap<Integer, Node> map;
private DoubleList cache;
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 value) {
    Node x = new Node(key, value);

    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 LRUCache {
    Map<Integer,Node> map ;//哈希表
    int maxCap;//记录最大缓存容量
    DoubleList list;//双向链表
    public LRUCache(int capacity) {
        map=new HashMap();
        this.maxCap=capacity;
        list=new DoubleList();
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
           return -1; 
        }
        
        put(key,map.get(key).val);//删除原来位置,并把数据提到开头
        return  map.get(key).val;

    }
    
    public void put(int key, int value) {
        Node node=new Node(key,value);
        if(map.containsKey(key)){
            list.remove(map.get(key));
            list.addFirst(node);
            //更新数据
            map.put(key,node);
        }else{
            //不包含 添加进去 看是容量满了
            if(list.size==maxCap){
                Node node2=list.removeLast();
                map.remove(node2.key);
            }
            map.put(key,node);
            list.addFirst(node);
        }
    }
}

class DoubleList{
    //跟LRU没关系现在,你就只写双向链表的就行
    //属性: 头结点 尾结点 长度
    Node head,tail;
    int size=0;

    public void addFirst(Node x){
        if(head==null){
            head=tail=x;
        }else{
             Node n = head;
            n.prev = x;
            x.next = n;
            head = x;
        }
        size++;
    }
     public void remove(Node x){
         if(head==x&&tail==x){
             head=null;
             tail=null;
         }else if(head==x){
             x.next.prev=null;
             head=x.next;
         }else if(tail==x){
             x.prev.next=null;
             tail=x.prev;
         }else{
             x.prev.next=x.next;
             x.next.prev=x.prev;
         }
         size--;
    }
    public Node removeLast(){
        Node node=tail;
        remove(tail);
        return node;
    }
    public int size(){
   
        return size;
    }
}

class Node{
    //Node属性有 key val  前驱节点  后继节点
    int key,val;
    Node prev,next;
    public Node(int key,int val){
        this.key=key;
        this.val=val;
    }
}