@H_406_2@class LRUNode{
    String key;
    Object value;
    LRUNode next;

    public LRUNode(String key, Object value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    LRUNode head;
    int size = 0;// 当前大小
    int capacITy = 0; // 最大容量(Linkedlist应该是负载因子乘以最大容量)

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public Object get(String key) {
        LRUNode cur = head;
        LRUNode PRe = head;// 指向要删除节点的前驱
        // 找到对应的节点，并把对应的节点放在链表头部
        // 先考虑特殊情况
        if(head == null)
            return null;
        if(cur.key.equals(key))
            return cur.value;
        // 进行查找
        cur = cur.next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        // 代表没找到了节点
        if (cur == null)
            return null;

        // 进行删除
        pre.next = cur.next;
        // 删除之后插入头结点
        cur.next = head;
        head = cur;
        return cur.value;
    }

    public void put(String key, Object value) {
        if (capacity == 1) {
            head = new LRUNode(key, value);
            this.size = 1;
        }
        LRUNode cur = head;
        LRUNode pre = head;
        // 先查看链表是否为空
        if (head == null) {
            head = new LRUNode(key, value);
            this.size = 1;
            this.print();
            return;
        }
        // 先查看该节点是否存在
        // 第一个节点比较特殊，先进行判断
        if (head.key.equals(key)) {
            head.value = value;
            this.print();
            return;
        }
        cur = cur.next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        // 代表要插入的节点的 key 已存在，则进行 value 的更新
        // 以及把它放到第一个节点去
        if (cur != null) {
            cur.value = value;
            pre.next = cur.next;
            cur.next = head;
            head = cur;
            this.print();
        } else {
            // 先创建一个节点
            LRUNode tmp = new LRUNode(key, value);
            // 该节点不存在，需要判断插入后会不会溢出
            if (size >= capacity) {
                // 直接把最后一个节点移除
                cur = head;
                while (cur.next != null && cur.next.next != null) {
                    cur = cur.next;
                }
                cur.next = null;
                tmp.next = head;
                head = tmp;
                this.print();
            } else {
                tmp.next = head;
                head = tmp;
                this.size ++;
                this.print();
            }
        }
    }

    public void print(){
        LRUNode cur = head;
        while(cur != null){
            System.out.print(cur.key + " ");
            System.out.print(cur.value + "  ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(4);
        lru.put("1", 1);
        lru.put("2", 2);
        lru.put("3", 3);
        System.out.println();
        System.out.println(lru.get("2"));
        lru.put("4", 4);
        lru.put("5", 5);
        lru.put("4", 444);
    }
}