146. LRU Cache.md

solution1 (hashmap & doubly linked list)

class LRUCache {
  static class Node {
        int key;
        int value;
        Node pre;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private Map<Integer, Node> map;
    int capacity;
    Node head;
    Node tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
    }

    public int get(int key) {
        if (map.containsKey(key)){
            Node cur = map.get(key);
            update(cur);
            return cur.value;
        }
        else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).value = value;
            update(map.get(key));
        }
        else {

            Node insert = new Node(key, value);
            insert(insert);
//            System.out.println("map size is " + map.size());
        }
    }
    private void insert(Node cur) {
        if (map.size() == capacity) {
            if (capacity == 0) {
                cur.next = tail;
                tail.pre = cur;
                head.next = cur;
                cur.pre = head;
            }
            else {
                // insert
                cur.next = head.next;
                head.next.pre = cur;
                head.next = cur;
                cur.pre = head;
                // remove least
                map.remove(tail.pre.key);
                Node left = tail.pre.pre;
                tail.pre = left;
                left.next = tail;
                // put into map
                map.put(cur.key, cur);

            }
        }
        else {
//            System.out.println(cur.key);
            map.put(cur.key, cur);
            cur.next = head.next;
            head.next.pre = cur;
            head.next = cur;
            cur.pre = head;
        }
    }
    private void update(Node cur) {
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
        cur.next = head.next;
        head.next.pre = cur;
        head.next = cur;
        cur.pre = head;
    }
}

note

• time O(1) for all operations / space O(n)
• The idea is to use hashmap to store key and its mapped node so we can access node in O(1) time, and use doubly linked list to achieve LRU cache functionality.