146. LRU Cache

Problem:

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

4/11/2018 update:
Use doubly linked list. Insert the most recently used node to head. So what's before tail is the least recently used. The purpose of hash table here is to enable O(1) operations.

思路：
hashtable在这道题里主要是为了检测key是否存在和size是否超过capacity。

class LRUCache {
    class DLinkedNode {
        int key;
        int val;
        DLinkedNode pre;
        DLinkedNode next;
        public DLinkedNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    DLinkedNode head;
    DLinkedNode tail;
    Map<key, DLinkedNode> map;
    int capacity;
    public LRUCache(int capacity) {
        head = new DLinkedNode(0, 0);
        tail = new DLinkedNode(0, 0);
        map = new HashMap<>();
        head.next = tail;
        tail.pre = head;
        this.capcity = capacity;
    }

    private void moveToHead(DLinkedNode node) {
        head.next.pre = node;
        node.next = head.next;
        node.pre = head;
        head.next = node;
    }

    private void remove(DLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public int get(int key) {
        DLinkedNode node = map.get(key);
        if (node != null) {
            // move to head
            remove(node);
            moveToHead(node);
            return node.val;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        if (node == null) {
            node = new DLinkedNode(key, value);
            map.put(key, node);
        } else {
            node.val = value;
            remove(node);
        }
        moveToHead(node);
        if (map.size() > capacity) {
            map.remove(tail.pre.key);
            remvoe(tail.pre);
        }
    }
}

/**
 * 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);
 */