【算法】LRU模拟

class LRUCache {

    //头
    private Node head;
    //尾
    private Node tail;
    //容量
    private int cap;

    private Map<Integer, Node> map;

    public LRUCache(int cap) {
        this.cap = cap;
        map = new HashMap<>();
    }

    public int get(int Key) {
        Node node = map.get(Key);
        if (node == null) {
            return -1;
        }
        moveNodeToTail(node);
        return node.value;
    }


    public void put(int k, int v) {
        Node node = map.get(k);
        if (node != null) {
            //更新并放置尾节点
            node.value = v;
            moveNodeToTail(node);
        } else {
            //不存在，则根据容量判断
            if (map.size() == cap) {
                //容量已满，移除队头元素
                int oldk = deleteNode(head);
                map.remove(oldk);
            }
            node = new Node(k, v);
            addNodeToTail(node);
            map.put(k, node);
        }
    }


    //添加节点至尾节点
    public void addNodeToTail(Node node) {
        if (tail != null) {
            tail.next = node;
            node.pre = tail;
            node.next = null;
        }
        tail = node;
        if (head == null) {
            head = node;
        }
    }

    //将指定节点移至链表尾部
    public void moveNodeToTail(Node node) {
        if (node == tail) {
            return;
        }
        //删除指定节点
        deleteNode(node);
        //将节点放置队尾
        addNodeToTail(node);
    }

    //移除节点
    public int deleteNode(Node node) {
        if (node == head && node == tail) {
            //如果只有一个节点
            head = null;
            tail = null;
        } else if (tail == node) {
            //如果是尾节点
            tail = node.pre;
            node.next = null;
        } else if (node == head) {
            //如果是头节点
            head = node.next;
            head.pre = null;
        } else {
            //中间节点
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }
        return node.key;
    }
}

class Node {
    Node pre;
    Node next;
    int key;
    int value;

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