image.png

解法

class LRUCache {

    class Node {

        Node pre;

        Node next;

        int key;

        int value;

        public Node() {

        }

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

    private Map<Integer, Node> map;

    private int capacity;

    private int size;

    private Node tail;

    private Node head;

    public LRUCache(int capacity) {
        map = new HashMap((int) Math.ceil(capacity / 0.75));
        this.capacity = capacity;
        this.size = 0;
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        // 链表调整
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                int k = removeTail();
                map.remove(k);
                size--;
            }
        }
        
    }

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

    private void moveToHead(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        addToHead(node);
    }

    private int removeTail() {
        Node pre = tail.pre;
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
        return pre.key;
    }
}