Problem

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.

方案一

1. HashMap + Heap<(timestamp. index)>
2. time complexity
   1. O(logn) time
   2. O(n) space

方案二

1. HashMap is definitely used
2. we need to modify the value or add a key value in O(1) , and we need to find the eldest pair in O(1)
   1. arraylist:
      1. fix capacity
      2. when inserting a node, need to move other existing nodes to their next position.
   2. linkedlist:
      1. head node: newest
      2. tail node: eldest
      3. how to find a specific value in O(1)
         1. we already have hashMap, it stores the key and node.

public class LRUCache {

    class ListNode {
        int key;
        int val;
        ListNode prev;
        ListNode next;

        public ListNode (int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    HashMap<Integer, ListNode> hash;
    ListNode headDummy;
    ListNode tailDummy;
    int cap;

    // @param capacity, an integer
    public LRUCache(int capacity) {
        hash = new HashMap<>();
        cap = capacity;
        headDummy = new ListNode(0, 0);
        tailDummy = new ListNode(0, 0);
        headDummy.next = tailDummy;
        tailDummy.prev = headDummy;
    }

    // @return an integer
    public int get(int key) {
        if (!hash.containsKey(key)) {
            return -1;
        }
        ListNode curt = hash.get(key);
        curt.prev.next = curt.next;
        curt.next.prev = curt.prev;
        updateToNewest(curt);
        return curt.val;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        if (hash.size() == cap && !hash.containsKey(key)) {
            deleteEldestNode();
        }
        ListNode node = null;
        if (!hash.containsKey(key)) {
            node = new ListNode(key, value);
            hash.put(key, node);
        } else {
            node = hash.get(key);
            node.val = value;
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        updateToNewest(node);
    }

    private void deleteEldestNode() {
        ListNode last = tailDummy.prev;
        if (last == headDummy) return;
        tailDummy.prev = last.prev;
        last.prev.next = tailDummy;
        hash.remove(last.key);
    }

    private void updateToNewest(ListNode node) {
        ListNode oldHead = headDummy.next;
        headDummy.next = node;
        node.prev = headDummy;
        node.next = oldHead;
        oldHead.prev = node;
    }
}