class LRUCache {

    class ListNode {

        int key;

        int val;

        ListNode next;

        ListNode pre;

        public ListNode(int key, int val) {

            this.key = key;

            this.val = val;

            next = null;

            pre = null;

        }

    }

    private int capacity;

    private List<ListNode> list;

    private int getId;

    private ListNode tail;

    private ListNode head;

    public LRUCache(int k) {

        capacity = k;

        list = new ArrayList<>();

        head = new ListNode(-1, -1);

        tail = new ListNode(-1, -1);

        head.next = tail;

        tail.pre = head;

    }

 // 二分查找

    public int search(int key) {

        int left = 0, right = list.size() - 1;

        while (left <= right) {

            int mid = left + (right - left) / 2;

            ListNode node = list.get(mid);

            if (node.key > key) {

                right = mid - 1;

            } else if (node.key < key) {

                left = mid + 1;

            } else {

                return mid;

            }

        }

        return -1;

    }

// get

    public int get(int key) {

        getId = search(key);

        if (getId == -1) {

            return getId;

        }

        ListNode node = list.get(getId);

        node.pre.next = node.next;

        node.next.pre = node.pre;

        addToTail(node);

        return node.val;

    }

// put

    public void put(int key, int val) {

        if (get(key) != -1) {

            list.get(getId).val = val;

            return;

        }

        ListNode node = new ListNode(key, val);

        addToTail(node);

        int i = 0;

        for (; i < list.size(); ++i) {

            if (list.get(i).key > key) {

                list.add(i, node); // 这里牵涉到get和add两个操作，不能保证put的时间复杂度为O(n)

                break;

            }

        }

        if (i == list.size()) list.add(node);

        if (list.size() > capacity) {

            getId = search(head.next.key);

            list.remove(getId);

            head.next = head.next.next;

            head.next.pre = head;

        }

    }

    public void addToTail(ListNode node) {

        node.pre = tail.pre;

        node.next = tail;

        node.pre.next = node;

        tail.pre = node;

    }

}