LRU缓存

146. LRU 缓存 - 力扣（LeetCode）

思路是用HashMap加双向链表来做

Class Node {

  Node prev;

  Node next;

  int key;

  int value;

  Node() {}

  Node(int key,int value) {

     this.key = key;

     this.value = value; 

}

}

HashMap里面放key和Node

get的时候，去hashmap里面查，如果能查到，把节点放到链表表头，返回值。

put的时候，

如果hashmap有值，就更新；

如果没有，把节点插入到表头，再判断长度是否超过容量，如果超过了容量，去掉链表最后节点，hashmap也要对应删除节点。

class LRUCache {

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

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

    Map<Integer, Node> nodeMap = new HashMap<>();
    int capacity;
    Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!nodeMap.containsKey(key)) {
            return -1;
        }
        Node now = nodeMap.get(key);
        remove(now);
        addToHead(now);
        return now.value;
    }

    public void put(int key, int value) {
        if (nodeMap.containsKey(key)) {
            Node now = nodeMap.get(key);
            now.value = value;
            remove(now);
            addToHead(now);
            return;
        }
        Node now = new Node(key, value);
        nodeMap.put(key, now);
        addToHead(now);
        if (nodeMap.size() > capacity) {
            cutTail();
        }
    }

    private void remove(Node now) {
        Node prevNode = now.prev;
        Node nextNode = now.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    private void addToHead(Node node) {
        Node firstNode = head.next;
        head.next = node;
        node.next = firstNode;
        firstNode.prev = node;
        node.prev = head;
    }

    private void cutTail() {
        Node lastNode = tail.prev;
        Node secNode = lastNode.prev;
        secNode.next = tail;
        tail.prev = secNode;
        nodeMap.remove(lastNode.key);
    }
}