下面的代码是一开始自己写的错误写法，不仅时间复杂度无法做到$O(1)$，（因为LinkedList的删除中间元素是$O(n)$），而且删除后LinkedList后序元素的下标也会改变，而key2index中的下标没有改变，所以会导致错误的结果。

//class LRUCache {
//    private final Map<Integer, Integer> key2value;
//    private final List<Integer> queue;
//    private final Map<Integer, Integer> key2index;
//    private final int capacity;
//
//    public LRUCache(int capacity) {
//        this.key2value = new HashMap<>();
//        this.queue = new LinkedList<>();
//        this.key2index = new HashMap<>();
//        this.capacity = capacity;
//    }
//
//    public int get(int key) {
//        if(key2value.containsKey(key)){
//            int idx = key2index.get(key);
//            queue.remove(idx);
//            queue.addLast(key);
//            key2index.put(key, queue.size() - 1);
//            return key2value.get(key);
//        }
//        return -1;
//    }
//
//    public void put(int key, int value) {
//        if(!key2value.containsKey(key)){
//            if(key2value.size() == capacity){
//                int removeKey = queue.removeFirst();
//                key2value.remove(removeKey);
//                key2index.remove(removeKey);
//            }
//            key2value.put(key, value);
//            queue.addLast(key);
//            key2index.put(key, queue.size() - 1);
//        } else {
//            int idx = key2index.get(key);
//            queue.remove(idx);
//            queue.addLast(key);
//            key2index.put(key, queue.size() - 1);
//            key2value.put(key, value);
//        }
//    }
//}

下面是用java的LinkedHashMap实现的代码，LinkedHashMap维护了一个双向链表和哈希表，具体细节在注释中

class LRUCache extends LinkedHashMap<Integer, Integer> {   // 直接继承LinkedHashMap
    private int capacity;                                  // cache容量

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true); // accessOrder设为true，就可以按照访问顺序排序双向链表，默认是插入顺序
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {                  // put后可能超出容量，LinkedHashMap会自动根据重写的removeEldestEntry删除最旧的元素
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

下面是手写的代码，使用了手写的双向链表（链表节点类和头尾哑节点）和直接将key映射到链表节点的HashMap，最近最少访问的节点位于head.next。不能用linkedList，因为它的remove只能是$O(n)$的，我们的remove需要直接操作指针达到$O(1)$。用哑节点是为了方便删除和插入的操作

class LRUCache {
    class LinkedListNode {
        int key;
        int value;
        LinkedListNode next;
        LinkedListNode prev;
        public LinkedListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private LinkedListNode head;
    private LinkedListNode tail;
    private final Map<Integer, LinkedListNode> map;
    private final int capacity;

    public LRUCache(int capacity) {
        head = new LinkedListNode(0, 0);
        tail = new LinkedListNode(0, 0);
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
        map = new HashMap<>();
    }

    public int get(int key) {
        if(map.containsKey(key)) {
            LinkedListNode node = map.get(key);
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = tail.prev;
            tail.prev.next = node;
            tail.prev = node;
            node.next = tail;
            return node.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if(map.containsKey(key)) {
            LinkedListNode node = map.get(key);
            node.value = value;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = tail.prev;
            tail.prev.next = node;
            tail.prev = node;
            node.next = tail;
        } else {
            if(map.size() == capacity) {
                LinkedListNode node = head.next;
                map.remove(node.key);
                head.next = node.next;
                node.next.prev = head;
            }
            LinkedListNode node = new LinkedListNode(key, value);
            map.put(key, node);
            node.prev = tail.prev;
            tail.prev.next = node;
            tail.prev = node;
            node.next = tail;
        }
    }
}