146. LRU Cache

使用 LinkedHashMap，这样 Key 的 order 就是添加进 Map 的顺序。
逻辑如下：

get function:
if key not in map, return -1
if key in map, remove key and add key, return value

put function:
if key in map, remove key and add (key, value)
if key not in map && map.size == capacity, remove first key and add (key, value)

代码如下：

class LRUCache {
    int capacity;
    LinkedHashMap<Integer, Integer> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>();
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        
        int value = map.remove(key);
        map.put(key, value);
        return value;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
        } else if (map.size() == capacity) {
            map.remove(map.entrySet().iterator().next().getKey());
        }
        map.put(key, value);
    }  
}

题解二的思路与上面一样，只不过使用 HashMap 和 self defined Double Linked List 来实现。
key => ListNode

// Double Linked List Node
class ListNode {
    int key;
    int value;
    ListNode prev;
    ListNode next;
    
    public ListNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache {
    int capacity;
    Map<Integer, ListNode> map;
    ListNode head = new ListNode(0, 0);
    ListNode tail = new ListNode(0, 0);
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } 

        ListNode node = map.get(key);
        moveToTail(node);

        return node.value;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            node.value = value;
            moveToTail(node);
        } else {
            if (map.size() == capacity) {
                ListNode first = head.next;
                head.next = first.next;
                first.next.prev = head;
                map.remove(first.key);
            }
            
            ListNode newNode = new ListNode(key, value);
            newNode.prev = tail.prev;
            tail.prev.next = newNode;
            newNode.next = tail;
            tail.prev = newNode;
            
            map.put(key, newNode);
        }
    }
    
    private void moveToTail(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;

        // move node to tail of list
        node.prev = tail.prev;
        tail.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }
}