Least Recently Used (LRU)

About

Least Recently Used is a caching mechanism. It evicts the least recently used item.

In LRU, you mix a Doubled Linked List with a HashMap.

• The Doubled Linked List is used to maintain the order for the accessed items. This is crucial to keep the trimCache() $O(1)$.

• The HashMap is used to access Linked List items in $O(1)$.

With this mix, you can access and update any cached values in constant time.

Implementation

type Node<T> = {
    value: T;
    next?: Node<T>,
    prev?: Node<T>
}

export default class LRU<K, V> {
    private length: number = 0;
    private head?: Node<T> | undefined = undefined;
    private tail?: Node<T> | undefined = undefined;
    private lookup = new Map<K, Node<V>>();
    private reverseLookup = new Map<Node<V>, K>();
    
    constructor(private capacity: number = 10) {}
    
    update(key: K, value?: V): void {
        let node = this.lookup.get(key);
        if (!node) {
            if (!value) return;
            node = { value } as Node<V>;
            this.length++;
            this.prepend(node);
            this.trimCache();
            this.lookup.set(key, node);
            this.reverseLookup.set(node, key);
        }
        // Key already exists
        else {
            this.detach(node);
            this.prepend(node);
            if (value) node.value = value;
        }
    }
    
    get(key: K): V | undefined {
        // Check cache for existance
        const node = this.lookup.get(key);
        if (!node) return undefined;
        
        // Update the value we found and move it to the front
        this.detach(node);
        this.prepend(node);
        
        // Return out the value found
        return node.value;
    }
    
    // Remove the node from its sequence on the List
    private detach(node: Node<V>): void {
        if (node?.prev) node.prev.next = node.next;
        if (node?.next) node.next.prev = node.prev;
        if (this.head === node) this.head = this.head?.next;
        if (this.tail === node) this.tail = this.tail?.prev;
        node.next = undefined;
        node.prev = undefined;
    }
    
    // Place the node to the List's head
    private prepend(node: Node<V>): void {
        if (!this.head) this.head = node;
        if (!this.tail) this.tail = node;
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }
    
    // Ensures that the Cache's size is not greater than the capacity
    private trimCache(): void {
        if (this.length <= this.capacity) return;
        const tail = this.tail;
        this.detach(this.tail);
        const tailKey = this.reverseLookup.get(tail);
        this.lookup.delete(key);
        this.reverseLookup.delete(tail);
        this.length--;
    }
}