Least Recently Used (LRU) cache

146 LRU Cache

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

LRU Cache

Problem Analysis

This is a Cache System with a capacity, we can get() or put() in O(1), if the element is prcessed, it will be moved to the latest element and if the number of elements exceed capacity, the least element will be poped out.
Find a element in a data structure in O(1) time -> HashTable
Add and Delete elements in O(1) time -> Doubly LinkedList

Algorithm Analysis

For our LRUCache Class there should have:

Map<Key, Node>
Node(Doubly List Node with key and value)
head pointer always points to the least element
tail pointer always points to the latest element
capacity

There are four possible situations:

Get

Find in the map -> Exist -> Return Value from the Map -> Find the Node in the List -> Move the node behind the Tail pointer (Dont need to move if its next pointer points to tail)
Find in the map -> Not Exist -> Return -1

Put

Find in the map -> Exist -> Set the value -> Find the Node in the List -> Change the value in the node(At the same time the node in the map will be changed) -> Move the node behind the Tail pointer (Dont need to move if its next pointer points to tail)
Find in the map -> Not Exist -> Check Capacity -> if cap == 0 cache the value of node next to head and remove it -> remove the value from map equal to the cache node -> if not -> create a new node -> add key and node in to the map -> add the node behind the tail -> capacity –

Time Complexity Analysis

Get() : O(1)
Put() : O(1)

Code Implementation

class LRUCache {
    
    private HashMap<Integer, Node> map;
    private int capacity;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        
        if(!map.containsKey(key)) {
            return -1;
        }
        
        Node targetNode = map.get(key);

        if(targetNode != tail.prev) {

            /* If the targetNode is the least element */
            if(targetNode == head.next) {
                head.next = head.next.next;
            } else {
                /* Remove the target targetNode from the current position */
                targetNode.prev.next = targetNode.next;
                targetNode.next.prev = targetNode.prev;
            }
            
            /* Update the new Tail to this node */
            tail.prev.next = targetNode;
            targetNode.prev = tail.prev;
            targetNode.next = tail;
            tail.prev = targetNode;
        }

        return targetNode.value;
    }

    public void put(int key, int value) {
        
        if(map.containsKey(key)) {
            Node targetNode = map.get(key);
            /* Update the value */
            targetNode.value = value;

            if(targetNode != tail.prev) {
                /* Remove the targetNode from current position */
                if(targetNode == head.next) {
                    head.next = head.next.next;
                } else {
                    targetNode.prev.next = targetNode.next;
                    targetNode.next.prev = targetNode.prev;
                }
                /* Move node to the latest */
                tail.prev.next = targetNode;
                targetNode.prev = tail.prev;
                targetNode.next = tail;
                tail.prev = targetNode;        
            }
        }
        else {
            Node newNode = new Node(key, value);
            
            /* If the capacity == 0, remove the least element */
            if(capacity == 0) {
                Node removedNode = head.next;
                head.next = head.next.next;
                map.remove(removedNode.key);
                capacity++;
            }
            /* Add the new node into the latest position */
            tail.prev.next = newNode;
            newNode.prev = tail.prev;
            newNode.next = tail;
            tail.prev = newNode;
            /* Add the node into the map */
            map.put(key, newNode);
            capacity--;
        }
    }
}

class Node {
    int key;
    int value;
    Node next;
    Node prev;
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}