LRU缓存

实际上底层维护双向链表和哈希表，将新查询的数据或插入的数据移动到链表头，若再插入数据时容量不足则从链表尾部删除

class LRUCache {
    Map<Integer, Node> map;
    DoubleLinkedList cache;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleLinkedList();
    }
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        int val = map.get(key).value;
        put(key, val);
        return val;
    }
    public void put(int key, int value) {
        Node newNode = new Node(key, value);
        if (map.containsKey(key)) {
            cache.delete(map.get(key));
            map.put(key, newNode);
            cache.addFirst(newNode);
        } else {
            if (capacity == map.size()) {
                int k = cache.deleteLast(newNode);
                map.remove(k);
            }
            cache.addFirst(newNode);
            map.put(key, newNode);
        }
    }
     class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
     class DoubleLinkedList {
        Node head;
        Node tail;
        public DoubleLinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
        }
        public void addFirst(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }
        public int delete(Node node) {
            int key = node.key;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            return key;
        }
        public int deleteLast(Node node) {
            if (tail.prev == head) return -1;
            return delete(tail.prev);
        }
    }
}