Untitled

class LinkedListNode {
    key: number;
    value: number;
    prev: LinkedListNode | null = null;
    next: LinkedListNode | null = null;

    constructor(key: number, value: number) {
        this.key = key;
        this.value = value;
    }
}

class LRUCache {
    private capacity: number;
    private cache: Map<number, LinkedListNode>;
    private head: LinkedListNode | null = null;
    private tail: LinkedListNode | null = null;

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

    // Retrieve a value from the cache
    get(key: number): number {
        const node = this.cache.get(key);
        if (!node) return -1;

        // Move the accessed node to the front (most recently used)
        this.moveToFront(node);

        return node.value;
    }

    // Insert or update a value in the cache
    put(key: number, value: number): void {
        let node = this.cache.get(key);

        if (node) {
            // Update the value and move it to the front
            node.value = value;
            this.moveToFront(node);
        } else {
            // Create a new node
            node = new LinkedListNode(key, value);
            if (this.cache.size >= this.capacity) {
                // Evict the least recently used (LRU) node
                if (this.tail) {
                    this.cache.delete(this.tail.key);
                    this.removeNode(this.tail);
                }
            }
            this.addToFront(node);
            this.cache.set(key, node);
        }
    }

    // Remove a node from the linked list
    private removeNode(node: LinkedListNode): void {
        if (node.prev) {
            node.prev.next = node.next;
        } else {
            this.head = node.next;
        }

        if (node.next) {
            node.next.prev = node.prev;
        } else {
            this.tail = node.prev;
        }
    }

    // Add a node to the front of the linked list
    private addToFront(node: LinkedListNode): void {
        node.next = this.head;
        node.prev = null;

        if (this.head) {
            this.head.prev = node;
        }

        this.head = node;

        if (!this.tail) {
            this.tail = node;
        }
    }

    // Move a node to the front of the linked list
    private moveToFront(node: LinkedListNode): void {
        this.removeNode(node);
        this.addToFront(node);
    }
}

// Example usage
const lruCache = new LRUCache(2);

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