LeetCode146. LRU 缓存机制

题目链接：LeetCode146展开目录

题解展开目录

基础数据结构的应用，HashMap 中存的是 key 和 Node，Node 中存的是 key 和 value

代码展开目录

class LRUCache {

    static class Node {
        int key;
        int value;
        public Node(int key, int value) {
            super();
            this.key = key;
            this.value = value;
        }
        Node pre;
        Node next;
    }
    public int capacity;
    public Map<Integer, Node> map;
    public Node head;//设一个虚拟的头结点
    public Node tail;//设一个虚拟的尾结点
    public int size;//链表长度
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.pre = null;
        head.next = tail;
        tail.pre = head;
        tail.next = null;
    }
    
    public void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    
    public void addToHead(Node node) {
        node.next = head.next;
        node.next.pre = node;
        node.pre = head;
        head.next = node;
    }
    
    public int get(int key) {
        int value = -1;
        if(map.get(key) != null){
            value = map.get(key).value;
            removeNode(map.get(key));
            addToHead(map.get(key));
        }
        return value;
    }
    
    public void put(int key, int value) {
        if(map.get(key) != null){
            removeNode(map.get(key));
            map.remove(key);
            size--;
        }
        Node node = new Node(key, value);
        map.put(key, node);
        if(size < capacity){
            addToHead(node);
            size++;
        } else{
            Node remove = tail.pre;
            removeNode(remove);
            map.remove(remove.key);
            addToHead(node);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */