LRUCache.ts

type Node<T> = {
    next: Node<T>;
    prev: Node<T>;
    key: number;
    value: T;
};

class LRUCache {
    private capacity: number;
    private size: number = 0;
    private cache: { [key: number]: Node<number> } = {};
    private root: Node<number> = null;
    private tail: Node<number> = null;

    constructor(capacity: number) {
        this.capacity = capacity;
    }

    get(key: number): number {
        const node = this.cache[key];
        
        if (!node) {
            return -1;
        }
        
        // Move this node to the beginning.
        this.remove(key);
        this.put(key, node.value);
        
        return node.value;
    }

    put(key: number, value: number): void {
        let node = this.cache[key];
        
        if (node) {
            // Update the node value.
            node.value = value;
            
            // Mark it used.
            this.get(key);
            return;
        }
                    
        this.size++;
        const prevRootNode = this.root;

        node = {
            prev: null as Node<number>,
            next: prevRootNode,
            key,
            value
        };

        if (prevRootNode) prevRootNode.prev = node;
        if (!this.tail) this.tail = node;
        this.root = node;
        this.cache[key] = node;
        
        if (this.size > this.capacity) {
            this.evictEldestEntry();
        }
    }
    
    private evictEldestEntry(): void {
        this.remove(this.tail.key);
    }
    
    private remove(key: number): void {
        this.size--;
        
        const node = this.cache[key];
        const prevNode = node.prev;
        const nextNode = node.next;

        node.next = null;
        node.prev = null;
        
        if (nextNode) nextNode.prev = prevNode;
        if (prevNode) prevNode.next = nextNode;
        
        if (this.root === node) {
            this.root = nextNode;
            if (nextNode) nextNode.prev = null;
        }

        if (this.tail === node) {
            this.tail = prevNode;
            if (prevNode) prevNode.next = null;
        }

        this.cache[key] = null;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

function print(root: Node<any>): string {
    const str = [];
    let i = 0;
    
    while(root && i < 10) {
        i++;
        str.push(root.key + '=' + root.value);
        root = root.next;
    }

    return str.join(', ');
}