August 27, 2019

146. LRU Cache

用双向链表实现一个LRU cache，这里自定义越靠近链表头的node，在越近的时间使用过。支持两个操作——get和set：

get(key)：如果链表中有key对应的node，返回该node的值，并把node移到链表头部（最近使用过）；如果没有，返回-1；
set(key,value)：如果链表中已经有key对应的node，修改对应node的值为value（但不需要把这个node放在头结点处）；如果链表中没有key对应的node，那么要新建node插入链表中，但此时要看链表是否还有空间。如果没有，就将尾部node（最少使用的node）删除，然后在头部插入新的node。为了提高查找效率，这里使用一个hashMap存放<key,node>键值对，这样就可以在O(1)的时间判断cache中是否存在对应的key。

这道题使用两个数据结构，doubly linked list 和 hashmap.
怎么想的：

要加要减：doubly linked list
还要使用哈希表因为要知道每个node而不是key，用hashmap存key和node的对应关系

注意删值的时候要先从map删，再删node。

Time: O(1) for both put and get; Space: O(capacity)

class Node {
    int key;
    int val;
    Node prev;
    Node next;
    
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    
    Node head;
    Node tail;
    Map<Integer, Node> map;
    int capacity;
    int size;

    public LRUCache(int capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        head.prev = null;
        tail.prev = head;
        tail.next = null;
        map = new HashMap<>();
        this.capacity = capacity;
        this.size = 0;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        deleteNode(node);
        insertToFront(node);
        return node.val;
    }
    
    public void put(int key, int val) {
        
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = val;
            deleteNode(node);
            insertToFront(node);
        } else {
            Node node = new Node(key, val);
            map.put(key, node);
            if (size >= capacity) {
                map.remove(tail.prev.key); // 一定要先 remove map 再 deleteNode 否则会报错!!
                deleteNode(tail.prev);
                insertToFront(node);
            } else {
                insertToFront(node);
                size++;
            }
        }
        
    }
    
    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void insertToFront(Node node) {
        Node next = head.next;
        head.next = node;
        node.prev = head;
        node.next = next;
        next.prev = 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);
 */