大体题解思路：

1. get方法和put方法时间复杂度要求是O(1)，因此第一想到使用map
2. 因为需要一个数据结构保证有序，因此会考虑到使用链表结构或者数组，而链表结构的移动的时间复杂度是O(1)，因此优选链表结构
3. 选定map+链表的结构。题目中要求map元素使用后要更新链表，将使用到的元素（包括get和put动作）放至首位，并且在缓存大小达到阈值的时候删除最后一个结点（即最久未使用节点）
4. 为了达到第三点的要求，需要使用双向链表来使得移动可以在O(1)时间复杂度内完成

import java.util.HashMap;

/**
 * LRU MAP+双向链表（通过链表来找最久未使用节点）
 * @date 2022/12/6
 * @since 1.0.0
 */
public class LRUCache {
    private DoubleLinkList doubleLinkList;
    private HashMap<Integer,Node> cache;
    private int cap;

    LRUCache(int cap){
        this.cap = cap;
        doubleLinkList = new DoubleLinkList();
        cache = new HashMap<>();
    }

    public int get(int key) {
        if(cache.containsKey(key)) {
            Node node =  cache.get(key);
            doubleLinkList.delNode(node);
            doubleLinkList.mvFirst(node);
            return node.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            cache.put(key,node);
            // 更新
            get(key);
        } else {
            if (cache.size() >= this.cap) {
                Node node = doubleLinkList.delLast();
                cache.remove(node.key);
            }
            Node newNode = new Node(key,value);
            doubleLinkList.mvFirst(newNode);
            cache.put(key,newNode);
        }

    }

}

class DoubleLinkList {
    public Node head;
    public Node tail;

    DoubleLinkList(){
        this.head = new Node(-1,-1);
        this.tail = new Node(-1, -1);
        head.pre = tail;
        head.next = tail;

        tail.pre = head;
        tail.next = head;
    }
    //  下面三个方法是操作重点
    void mvFirst(Node node) {
        // 移动至头节点
        node.pre = head;
        node.next = head.next;

        head.next.pre = node;
        head.next = node;
    }

    Node delNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }

    Node delLast(){
        // 注意边界值,当不存在节点时
        if (head.next == tail) return tail;
        return delNode(tail.pre);
    }

}

class Node{
    public Integer key;
    public Integer value;
    public Node pre;
    public Node next;

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

Q.E.D.