LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution: HashMap + Double Linked List

LRU Cache: 经常用的放在前面，用的少的放在后面。这样当资源超过cache的容积的时候就可以把用得最少的资源删掉。这就要求我们要对节点有好的删除和插入操作 --> LinkedList.

用一个hashmap来维护结点的位置关系，hashmap的key就是资源本身的key，value是资源的结点（包含key和value的信息）。

把node维护成一个双向链表构成的队列，这样子如果我们要访问某一个结点，那么可以通过hash表和key来找到结点，从而取到相应的value。而当我们想要删除或者插入结点时，我们还是通过hash表找到结点，然后通过双向链表和队列的尾结点把自己删除同时插入到队尾。

通过hash表访问结点我们可以认为是O(1)的操作，然后双向链表的插入删除操作也是O(1)的。所以用O(1)时间来完成所有LRU cache的操作。空间上就是对于每一个资源有一个hash表的的项以及一个对应的结点（包含前后指针和资源的<key, value>）。

public class LRUCache {
    //DoubleLinkedListNode constructor
    class DoubleLinkedListNode {
        int val;
        int key;
        DoubleLinkedListNode pre;
        DoubleLinkedListNode next;
        
        public DoubleLinkedListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    private DoubleLinkedListNode first;
    private DoubleLinkedListNode last;
    private HashMap map;  //key is the key, value is the node which contains its key&value
    private int capacity;
    private int num;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        num = 0;
        first = null;
        last = null;
        map = new HashMap();
    }
    
    public int get(int key) {
        DoubleLinkedListNode node = map.get(key);
        if(node == null) {  //key doesn't exist
            return -1;
        }else if(node != last) {
            if(node == first) {
                first = first.next;
            }else {
                node.pre.next = node.next;
            }
            node.next.pre = node.pre;
            last.next = node;
            node.pre = last;  // move node to the last one
            node.next = null;
            last = node;
        }
        return node.val;
    }
    
    public void set(int key, int value) {
        DoubleLinkedListNode node = map.get(key);
        if(node != null) {  // if first node exists, asign value to it and move to the last one (相当于删除了第一个node)
            node.val = value;
            if(node != last) {
                if(node == first) {
                    first = first.next;
                }else {
                    node.pre.next = node.next;
                }
                node.next.pre = node.pre;
                last.next = node;
                node.pre = last;
                node.next = null;
                last = node;
            }
        }else {
            DoubleLinkedListNode newNode = new DoubleLinkedListNode(key, value);
            
            if(num >= capacity) {
                map.remove(first.key);
                first = first.next;
                if(first != null) {
                    first.pre = null;
                }else {
                    last = null;
                }
                num--;
            }
            
            if(first == null || last == null) {
                first = newNode;
            }else {
                last.next = newNode;
            }
            newNode.pre = last;
            last = newNode;
            map.put(key, newNode);  // don't forget to add the newNode into map
            num++;
          }
    }
}