LRUCacheGoodVersion.java

public class LRUCacheGoodVersion {

    public class Node {
        public int val;
        public int key;
        public Node pre = null;
        public Node next = null;

        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }

    // encapsulates a DoublyList class
    public class DoublyList {
        // for doubly linked list, keep two dummies, head and tail
        Node dummyHead = null;
        Node dummyTail = null;

        public void addLast(Node node) {
            node.pre = this.dummyTail.pre;
            this.dummyTail.pre.next = node;
            this.dummyTail.pre = node;
            node.next = this.dummyTail;
        }

        public Node getHead() {
            return this.dummyHead.next;
        }

        public void remove(Node n) {
            n.pre.next = n.next;
            n.next.pre = n.pre;
            n.pre = null;
            n.next = null;
        }

        public DoublyList() {
            this.dummyHead = new Node(Integer.MIN_VALUE, -1);
            this.dummyTail = new Node(Integer.MIN_VALUE, -1);

            this.dummyHead.next = this.dummyTail;
            this.dummyTail.pre = this.dummyHead;    // head <-> last, this is what i like about two dummy nodes
        }
    }

    private int capacity;
    private Map<Integer, Node> lookup = null;
    private DoublyList list = null;

    public LRUCacheGoodVersion(int capacity) {
        this.capacity = capacity;
        this.lookup = new HashMap<Integer, Node>();
        this.list = new DoublyList();
    }

    public int get(int key) {
        if (this.lookup.containsKey(key)) {
            Node n = this.lookup.get(key);
            this.promoteToLast(n);
            return n.val;
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if (this.lookup.containsKey(key)) {
            Node n = this.lookup.get(key);
            n.val = value;
            this.promoteToLast(n);
            return;
        }

        if (this.lookup.size() == this.capacity) {
            Node leastUsed = this.list.getHead();
            this.list.remove(leastUsed);
            this.lookup.remove(leastUsed.key);
        }

        Node n = new Node(key, value);
        this.lookup.put(key, n);
        this.list.addLast(n);
    }

    private void promoteToLast(Node n) {
        this.list.remove(n);
        this.list.addLast(n);
    }
}