class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(0, 0, null, null);
        map = new HashMap<>(capacity);
    }

    public int get(int key) {
        Node node = getNode(key);
        if (node == null) {
            return -1;
        }
        return node.value;
    }

    private Node getNode(int key) {
        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        moveHead(node);
        return node;
    }

    private void moveHead(Node node) {
        if (node != head.next) { // 判断当前是否已经是在头部
            Node prev = node.prev;
            Node next = node.next;

            if (node == tail) {
                // 如果此时是最后一个，则修改尾节点
                // 这里不用担心tail=head
                tail = node.prev;
            } else {
                next.prev = node.prev;
            }

            // 将node插入到head之后

            node.prev = head;
            prev.next = next;

            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }
    }

    public void put(int key, int value) {
        Node node = getNode(key); // 获取node并移动到最前面
        if (node == null) {
            node = new Node(key, value, head, head.next); // 直接插入到最前面
            if (head.next != null) {
                head.next.prev = node;
            }
            head.next = node;

            if (tail == null) {
                tail = node; // tail初始化
            }

            map.put(key, node);

            if (map.size() > capacity) {
                // 如果加入后大于最大容量，则移除最后一个
                evict();
            }
        } else {
            node.value = value;
        }
    }

    public boolean evict() {
        if (tail != null) {
            map.remove(tail.key);
            tail.prev.next = null;
            tail = tail.prev == head ? null: tail.prev;
            return true;
        }
        return false;
    }

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

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

        public String toString() {
            return String.format("[%d, prev=%d, next=%s]", key, prev == null ? null : prev.value, next);
        }
    }

    public String toString() {
        return String.format("---
\nhead=%s\ntail=%s\n---
", head, tail);
    }

}