题解 | #设计LRU缓存结构#

import java.util.*;


public class Solution {
    class LinkNode {
        LinkNode prev;
        LinkNode next;
        int key;
        int val;
        public LinkNode() {}
        public LinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    LinkNode head;
    LinkNode tail;
    int capacity;
    int size;
    Map<Integer, LinkNode> mCache = new HashMap<>();
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.head = new LinkNode();
        this.tail = new LinkNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // write code here
        LinkNode node = mCache.get(key);
        if (null == node)return -1;
        removeNode(node);
        addToHead(node);
        return node.val;
    }

    public void set(int key, int value) {
        // write code here
        LinkNode node = mCache.get(key);
        if (null == node) {
            node = new LinkNode(key, value);
            addToHead(node);
            mCache.put(key, node);
            size++;
            if (size > capacity) {
                LinkNode tailNode = removeTail();
                mCache.remove(tailNode.key);
                size--;
            }
        } else {
            node.val = value;
            removeNode(node);
            addToHead(node);
        }
    }

    private void addToHead(LinkNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(LinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private LinkNode removeTail() {
        LinkNode node = tail.prev;
        removeNode(node);
        return node;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */