/**
 * 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.
 * (get means use, so we need to update)
 *
 * 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.
 *
 * Tags: Data Structure
 */
class LRUCache {

    /**
     * Doubly linked list node
     */
    static class Node{
        Node next;
        Node prev;
        int key;
        int val;

        Node (int key, int val) {
            this.key = key;
            this.val = val;s
        }

        /**
         * Delete current node
         */
        private void delete() {
            prev.next = next;
            if (next != null) next.prev = prev;
        }

        /**
         * Add current node to preNode's next
         */
        private void addAfter(Node preNode) {
            next = preNode.next;
            if (next != null) next.prev = this;
            preNode.next = this;
            prev = preNode;
        }
    }

    Node dummy = new Node();
    Node tail = dummy;
    Map<Integer, Node> cache = new HashMap<Integer, Node>();
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n = cache.get(key);
        moveToTail(n);
        return n.val;
    }

    /**
     * Check key in map or not
     * If in map, get node, update value, and move to tail
     * If not, create node, put in cache, and add to tail
     * If capacity exceeds, remove head from map and delete
     */
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node n = cache.get(key);
            n.val = value;
            moveToTail(n);
            return;
        }
        Node n = new Node(key, value); // add new node
        cache.put(key, n);
        addToTail(n); // update usage

        if (cache.size() > capacity){
            n = dummy.next;
            cache.remove(n.key);
            n.delete(); // delete dummy
        }
    }

    private void moveToTail(Node n){
        if (n == tail) return;
        n.delete(); // unlink node with other nodes first
        addToTail(n); // add it to tail
    }

    /**
     * Add node after tail and update tail to that node
     */
    private void addToTail(Node n){
        n.addAfter(tail);
        tail = n;
    }

    /**
     * TLE, use two lists and sync manually
     */
    class LRUCacheOwn {

        List<Integer> keys = null;
        List<Integer> values = null;
        int capacity = -1;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.keys = new ArrayList<Integer>(capacity);
            this.values = new ArrayList<Integer>(capacity);
        }

        public int get(int key) {
            int index = keys.indexOf(key);
            if (index == -1) {
                return -1;
            }
            keys.remove(index);
            keys.add(key);
            int v = values.remove(index);
            values.add(v);
            return v;
        }

        public void set(int key, int value) {
            int index = keys.indexOf(key);
            if (index != -1) {
                keys.remove(index);
                values.remove(index);
            } else if (keys.size() >= capacity) {
                keys.remove(0);
                values.remove(0);
            }
            keys.add(key);
            values.add(value);
        }
    }
}

@@ -532,20 +532,332 @@
 ructure%0A
+ * %0A * Use 2 data structures to implement an LRU Cache%0A * 1. A Queue which is implemented using a doubly linekd list. The max size of %0A * the queue will be equal to cache size. Put most recently used at the end%0A * 2. A Hash with Node's value as key and the Node as value%0A * 3. A dummy head for Doubly LinkedList%0A
  */%0A
-
 class LR
@@ -1767,24 +1767,194 @@
 ity;%0A    %7D%0A%0A
+    /**%0A     * Check key in map%0A     * If not in map, return -1%0A     * If in map, update usage by getting node and moving it to tail%0A     * Then return its value%0A     */%0A
     public i
@@ -2250,32 +2250,82 @@
 and add to tail%0A
+     * Capacity can exceed when adding a new node%0A
      * If capaci
@@ -2848,24 +2848,70 @@
    %7D%0A    %7D%0A%0A
+    /**%0A     * Delete and add to tail%0A     */%0A
     private 
@@ -3205,16 +3205,16 @@
 (tail);%0A
+
         
@@ -3232,1108 +3232,7 @@
    %7D
-%0A%0A    /**%0A     * TLE, use two lists and sync manually%0A     */%0A    class LRUCacheOwn %7B%0A%0A        List%3CInteger%3E keys = null;%0A        List%3CInteger%3E values = null;%0A        int capacity = -1;%0A%0A        public LRUCache(int capacity) %7B%0A            this.capacity = capacity;%0A            this.keys = new ArrayList%3CInteger%3E(capacity);%0A            this.values = new ArrayList%3CInteger%3E(capacity);%0A        %7D%0A%0A        public int get(int key) %7B%0A            int index = keys.indexOf(key);%0A            if (index == -1) %7B%0A                return -1;%0A            %7D%0A            keys.remove(index);%0A            keys.add(key);%0A            int v = values.remove(index);%0A            values.add(v);%0A            return v;%0A        %7D%0A%0A        public void set(int key, int value) %7B%0A            int index = keys.indexOf(key);%0A            if (index != -1) %7B%0A                keys.remove(index);%0A                values.remove(index);%0A            %7D else if (keys.size() %3E= capacity) %7B%0A                keys.remove(0);%0A                values.remove(0);%0A            %7D%0A            keys.add(key);%0A            values.add(value);%0A        %7D%0A    %7D
 %0A%7D%0A

Update LRUCache