146.LRU缓存.md

LRU的主要关心的问题就是只要我们对某一个数据进行了操作（无论是get还是put操作），都要将这个key所对应的链表节点提前到最前面，最后的链表节点就是当size达到capacity时进行淘汰的节点。

class LRUCache {

    class DLinkedNode {
        int key;
        int val;
        DLinkedNode pre, next;
        DLinkedNode(){}
        DLinkedNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    Map<Integer, DLinkedNode> map = new HashMap<>();
    int capacity;
    int size;
    DLinkedNode head, tail;

    public LRUCache(int _capacity) {
        capacity = _capacity;
        size = 0;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        DLinkedNode node = map.get(key);
        moveToHead(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            DLinkedNode node = map.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            DLinkedNode node = new DLinkedNode(key, value);
            size++;
            if (size > capacity) {
                DLinkedNode removed = removeTailNode();
                map.remove(removed.key);
                size--;
            }
            addToHead(node);
            map.put(key, node);
        }
    }

    public void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    public void addToHead(DLinkedNode node) {
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    public void removeNode(DLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public DLinkedNode removeTailNode() {
        DLinkedNode removed = tail.pre;
        removeNode(removed);
        return removed;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */