Stack Solution - LRU Cache

The basic idea is to use a LinkedList to maintain the used frequency, latest used will be re-inserted to the tail, and when set and full, the head will be removed. Two global Node created as head and tail, and the map is used to locate the node, both the value and position in LinkedList.

The tough part is to come up with an idea that define a personal node with value and left/right pointers, use the new defined node to maintain the LinkedList.


public class LRUCache {

    public LRUCache(int capacity) {
        mCapacity = capacity;
    }

    public int get(int key) {

        if (!mKeyValueNodeMap.containsKey(key))
            return -1;

        Node node = mKeyValueNodeMap.get(key);

        if (node.next != null) {
            if (node.prev == null) { // the head node
                mHead = node.next;
            } else {
                node.prev.next = node.next;
            }
            node.next.prev = node.prev;

            node.prev = mTail;
            node.next = null;
            mTail.next = node;
            mTail = node;
        }

        return node.val;
    }

    public void set(int key, int value) {

        if (mKeyValueNodeMap.containsKey(key)) {
            get(key); // only to move it to the tail
            mKeyValueNodeMap.get(key).val = value;
        } else {      
            Node node = new Node(key, value);

            // invalidate the LRU item, meaning remove the head element
            if (mKeyValueNodeMap.size() >= mCapacity) {
                if (mHead != null) {
                    Node oldHead = mHead;
                    mHead = mHead.next;
                    oldHead.next = null;
                    if (mHead != null) // it could be only one item
                        mHead.prev = null;
                    mKeyValueNodeMap.remove(oldHead.key);
                }
            }

            // insert the new value
            if (mHead == null) {
                mHead = node;
                mTail = node;
            } else {
                mTail.next = node;
                node.prev = mTail;
                mTail = node;
            }
            mKeyValueNodeMap.put(key, node);
        }
    }

    private class Node {

        int key;
        int val;
        Node prev = null;
        Node next = null;
        Node(int k, int v) {
            key = k;
            val = v;
        }  
    }

    HashMap<Integer, Node> mKeyValueNodeMap = new HashMap<Integer, Node>();
    Node mHead = null;
    Node mTail = null;
    int mCapacity = 0;
}