Problem Description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:

Could you do both operations in O(1) time complexity?

Example

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

Analysis

We are asked to design a LRU structure with get and put function and both functions should be in O(1) time complexity. Let’s consider these two functions first:

• get

  • If the key exists, return the value, and make the key-value pair be the newest

  • if key doesn’t exist, return -1

• put

  • if the key exists, just update the value, and make the key-value pair be the newest

  • if the key doesn’t exist

    • if the cache reaches capacity, delete the oldest key-value pair, add the new key-value pair to the newest

    • if not, just add the new key-value pair to the newest

It seems like we need to finish the following assistant functions:

• make the key-value pair be the newest

• delete the oldest key-value pair

Now let’s consider the data structure we will use for this problem. To make get, put, and remove to O(1) time, the HashMap is good. However, to achieve ‘make the key-value pair be the newest’, we may need to change the position of the element, HashMap cannot deal with the order, ArrayList and LinkedList are the choices. Consider this problem, we only need to move the key-value pair to the newest, which means to the top, the LinkedList seems a better choice. Therefore, here we are supposed to use both HashMap and LinkedList. How to do that?

The problem can be solved with a HashTable that keeps track of the key and its values in the double linked list. We use HashMap to deal with get and put, meanwhile, we use double linked list to handle the position of the element. Here is the solution:

Solution

First, build a data structure DlinkedNode

class DlinkedNode {
    DlinkedNode pre;
    DlinkedNode next;
    int key;
    int value;
}

Then finish the function

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
class LRUCache {
    private HashMap<Integer, DlinkedNode> cache;
    private int cap;
    private DlinkedNode head, tail;

    public LRUCache(int capacity) {
        cache = new HashMap<Integer, DlinkedNode>();
        cap = capacity;
        head = new DlinkedNode();
        tail = new DlinkedNode();
        head.pre = null;
        head.next = tail;
        tail.pre = head;
        tail.next = null;
    }

      // get
    public int get(int key) {
        DlinkedNode node = cache.get(key);
        if (node == null) return -1;
        makeNewest(node);
        return node.value;
    }

      // put
    public void put(int key, int value) {
        DlinkedNode node = cache.get(key);

        if (node == null) {
            node = new DlinkedNode();
            node.key = key;
            node.value = value;

            if (cache.size() >= cap) {
                DlinkedNode rm = removeOldest();
                cache.remove(rm.key);
            }

            cache.put(key, node);
            addNode(node);
        } else {
            node.value = value;
            makeNewest(node);
        }

    }

      // remove node from the double linked list
    private void removeNode(DlinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

      // add new node to the top
    private void addNode(DlinkedNode node) {
        node.next = head.next;
        node.next.pre = node;
        node.pre = head;
        head.next = node;
    }

      // make a node be newest
    private void makeNewest(DlinkedNode node) {
        removeNode(node);
        addNode(node);
    }

      // remove the oldest node
    private DlinkedNode removeOldest() {
        DlinkedNode node = tail.pre;
        removeNode(node);
        return node;
    }
}

Complexity:

• Time: both get and put are O(1)

• Space: O(n)