LRU Cache | Leetcode

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

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

set(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.

---

Solution: The key here is to choose a data structure, or a group of data structures, that will support an efficient implementation of the LRU cache.

For a cache get and set, we need to support an O(1) time lookup and removal of a given key, which basically means that we would need a hashmap. We also need a way to quickly remove the key from an ordered list and then move it to the front of the ordered list. For this, we can use a doubly-linked list for quick insertions and removals when given any node. The insertion and removal should also require only O(1) time, which means that we need to use the hashmap to point to the doubly-linked list node, and not just to the integer value.

For the doubly-linked list, we need to maintain both the head pointer and tail pointer, so that we can quickly insert at the front and also remove the tail node without needing to go through the entire list.

We also need to maintain the number of elements in the LRU cache so that we can remove the oldest node when we reach the maximum capacity. We use the Java hashmap to maintain the size so that we do not have to roll our own variable.

Most of the code turns out to be manipulation operations around the doubly-linked list. The other parts are relatively straightforward.

public class LRUCache {
    
    private static class ListNode {
        int key;
        int value;
        ListNode prev;
        ListNode next;
        ListNode(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private ListNode head;
    private ListNode tail;
    private Map<Integer, ListNode> map = new HashMap<>();
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        ListNode node = map.get(key);
        if (node == null) return -1;
        
        // Move this node to the head of the list.
        if (node != head) {
            // (head != tail) must be true at this point.
            node.prev.next = node.next;
            if (tail == node) {
                tail = node.prev;
            } else {
                node.next.prev = node.prev;
            }
            node.prev = null;
            node.next = head;
            head.prev = node;
            head = node;
        }
        
        return node.value;
    }
    
    public void set(int key, int value) {
        // Check existing node for key.
        ListNode node = map.get(key);
        
        if (node != null) {
            // Reuse this node.
            node.value = value;
                
            // Short-circuit when key is already the head node.
            if (node == head) return;
            
            // Remove the old node for key.
            node.prev.next = node.next;
            if (tail == node) {
                tail = node.prev;
            } else {
                node.next.prev = node.prev;
            }
        } else if (map.size() == capacity) {
            // Remove the last node if we have reached capacity.
            map.remove(tail.key);
            
            // Reuse the tail node.
            node = tail;
            node.key = key;
            node.value = value;
            map.put(key, node);

            // Short-circuit if this is the only node in the list.
            if (head == tail) return;
            
            // Remove tail node.
            tail = tail.prev;
            tail.next = null;
        } else {
            // Create a new node as there is none we could reuse.
            node = new ListNode(key, value);
            map.put(key, node);
        }

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