LRU Cache

1package pkg5leetcode.interview150;2 3/*4 * LRU Cache | LC 1465 * APPROACH: HashMap + doubly linked list for O(1) get/put eviction.6 * COMPLEXITY: Time O(1) per op, Space O(capacity)7 */8import java.util.*;9 10public class interview150_LC146LRUCache {11    static class LRUCache {12        static class Node {13            int key, val;14            Node prev, next;15            Node(int k, int v) { key = k; val = v; }16        }17 18        final int cap;19        final Map<Integer, Node> map = new HashMap<>();20        final Node head = new Node(0, 0), tail = new Node(0, 0);21 22        LRUCache(int capacity) {23            cap = capacity;24            head.next = tail;25            tail.prev = head;26        }27 28        int get(int key) {29            if (!map.containsKey(key)) return -1;30            Node n = map.get(key);31            remove(n);32            insert(n);33            return n.val;34        }35 36        void put(int key, int value) {37            if (map.containsKey(key)) {38                Node n = map.get(key);39                n.val = value;40                remove(n);41                insert(n);42            } else {43                if (map.size() == cap) {44                    map.remove(tail.prev.key);45                    remove(tail.prev);46                }47                Node n = new Node(key, value);48                map.put(key, n);49                insert(n);50            }51        }52 53        void remove(Node n) {54            n.prev.next = n.next;55            n.next.prev = n.prev;56        }57 58        void insert(Node n) {59            n.next = head.next;60            n.prev = head;61            head.next.prev = n;62            head.next = n;63        }64    }65 66    public static void main(String[] args) {67        LRUCache cache = new LRUCache(2);68        cache.put(1, 1);69        cache.put(2, 2);70        check(cache.get(1) == 1, "case1");71        cache.put(3, 3);72        check(cache.get(2) == -1, "case2");73        cache.put(4, 4);74        check(cache.get(1) == -1 && cache.get(3) == 3 && cache.get(4) == 4, "case3");75        System.out.println("all tests passed");76    }77 78    static void check(boolean cond, String name) {79        if (!cond) throw new AssertionError("FAILED: " + name);80        System.out.println("  PASS " + name);81    }82}