146. 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.

思路: 设计LRU Cache， 需要先定义一个双链表结构，同时我们希望查找的时间复杂度为O(1)， 这样的话，我们需要个HashMap，来记录存的值, key为所插入的key，value为所存的node。其中，我们定义链表的头部为旧的元素， 尾部为最新的元素。
对于以下操作，
当set一个元素，hashmap的size< capacity的时候，我们之间将这个元素插入链表尾部。
当set一个元素，这个元素已经存在于hashMap中的时候，我们需要将这个元素的value更新，并且更新hashmap的索引，最后把这个元素拿出来，插到尾部。
当get一个元素的时候，我们需要返回这个元素值得同时，把这个元素拿出来，放到链表尾部。

public class LRUCache {
    private HashMap<Integer, Node> cache;
    private int capacity;
    private Node head;
    private Node tail;

    public class Node {
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
            pre = null;
            next = null;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        head.pre = null;
        tail.pre = head;
        tail.next = null;
    }

    public void detach(Node node) { // detach from head
        node.next.pre = node.pre;
        node.pre.next = node.next;
        node.pre = null;
        node.next = null;
    }

    public void attach(Node node) {
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
        node.next = tail;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node != null) {
            detach(node);
            attach(node);
        }
        return node == null ? -1 : node.value;
    }

    public void set(int key, int value) {
        Node node = cache.get(key);
        if (node != null) { // node existing
            node.value = value;
            cache.replace(key, node); // update value
            detach(node);
            attach(node);
        } else {
            Node temp = new Node(key, value);
            if (cache.size() == capacity) {
                cache.remove(head.next.key, head.next);
                detach(head.next);
            } 
            cache.put(key, temp);
            attach(temp);
        }
    }
}