一. 题目

二. 思路

三. 代码

class LRUCache
{
    private static class Node
    {
        int k, v;
        Node pre, ne;

        public Node()
        {
        }

        public Node(int k, int v)
        {
            this.k = k;
            this.v = v;
        }
    }

    private final Map<Integer, Node> kn;
    private final Node head, tail;
    private int size, cap;

    public LRUCache(int capacity)
    {
        this.size = 0;
        this.cap = capacity;
        kn = new HashMap<>(capacity);
        head = new Node();
        tail = new Node();
        head.ne = tail;
        tail.pre = head;
    }

    public int get(int key)
    {
        Node t = kn.get(key);
        if (t == null) return -1;
        moveToHead(t);
        return t.v;
    }

    public void put(int key, int value)
    {
        Node ot = kn.get(key), nt = new Node(key, value);
        kn.put(key, nt);
        addToHead(nt);
        if (ot != null) delNode(ot);
        else if (++size > cap)
        {
            --size;
            kn.remove(tail.pre.k);
            delNode(tail.pre);
        }
    }

    private void addToHead(Node t)
    {
        t.pre = head;
        t.ne = head.ne;
        head.ne = t;
        t.ne.pre = t;
    }

    private void delNode(Node t)
    {
        t.pre.ne = t.ne;
        t.ne.pre = t.pre;
    }

    private void moveToHead(Node t)
    {
        delNode(t);
        addToHead(t);
    }
}