import java.util.HashMap;

import java.util.Map;

public class lru {

    private class ListNode {  //双链表节点数据结构

        int key;

        int val;

        ListNode pre;

        ListNode next;

        public  ListNode(int key, int val) {

            this.key = key;

            this.val = val;

            pre =null;

            next =null;

        }

    }

    private int capacity;//链表容量

    private Mapmap; //查找数据在不在链表里面的hash表

    private ListNodehead;

    private ListNodetail;

    public lru(int capacity) { //初始化双链表数据结构

        this.capacity = capacity;

        map =new HashMap<>();

        head =new ListNode(-1, -1); //head与tail不是严格意义上的节点，只是一种数据结构

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

        head.next =tail;

        tail.pre =head;

    }

    public int get(int key) {  //从map（ hash表 ）中找到key，并插到链表尾部

        if(!map.containsKey(key)) {

            return -1;

        }

        ListNode node =map.get(key);

        node.pre.next = node.next; //把找到的这个节点删除

        node.next.pre = node.pre; //把找到的这个节点删除

        moveToTail(node); //再接到尾部

        return node.val;

    }

private void moveToTail(ListNode node) {  //将node节点移到尾部

        node.pre =tail.pre;

        tail.pre = node;

        node.pre.next = node;

        node.next =tail;

   }

    public void put(int key, int value) { //LRU总思想

        //直接调用这边的get方法，如果存在，它会在get内部被移动到尾巴，不用再移动一遍,直接修改值即可

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

            map.get(key).val = value;

            return;

        }

        //在hash表中不存在该数据，则new一个出来,如果超出容量，把头去掉

        ListNode node =new ListNode(key, value);

        map.put(key, node);

        moveToTail(node);

        if(map.size() >capacity) {

            map.remove(head.next.key);

            head.next =head.next.next;

            head.next.pre =head;

        }

    }

}