【算法】Java实现LRU Cache 缓存 LeetCode146

最近最少使用的缓存。

实现思想：借用双链表和map实现，双链表保存实际的值，map用来保存key和链表节点的映射关系。

class LRUCache {
    int capacity;
    // 保护节点
    Node head;
    Node tail;
    Map cache = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        // 如果没有返回 - 1，
        if(!cache.containsKey(key)) return -1;
        // 存在，则访问的放到头结点后，移除旧节点
        Node node = cache.get(key);
        remove(node);
        insert(head, node);
        return node.value;
    }
    
    public void put(int key, int value) {
        // 包含值，则更新新的值
        if(cache.containsKey(key)){
            remove(cache.get(key));
        } else {
            // 插入新值，判断是否超过容量，超过容量，删除tail的前一个
            if(cache.size() == capacity) {
                cache.remove(tail.pre.key);
                remove(tail.pre);
            }
        }
        Node node = new Node(key, value);
        insert(head, node);
        cache.put(key, node);

    }

    void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    void insert(Node o, Node n) {
        // 分别维护插入节点和前后节点的关系
        o.next.pre = n; n.next = o.next;
        o.next = n; n.pre = o;
    }

   
}

 class Node {
     int key;
     int value;
     Node pre;
     Node next;

     public Node() {
     }

     public Node(int key, int value) {
         this.key = key;
         this.value = value;
     }
 }