SOURCE

class LRUCache2 {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();

        this.head = null;
        this.tail = null;
    };

    createNode(key,value,ttl) {
        const now = Date.now();
        const expiredTime = now + ttl;

        return {
            key,
            value,
            expiredTime,
            prev:null,
            next:null,
        };
    };

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

    moveNode(node) {
        const prevNode = node.prev;
        const nextNode = node.next;

        if(prevNode) {
            prevNode.next = nextNode;
        }else {
            this.head = nextNode;
        }

        if(nextNode) {
            nextNode.prev = prevNode;
        }else{
            this.tail = prevNode;
        };

        node.prev = null;
        node.next = null;
    };

    moveNodeToHead(node) {
        this.moveNode(node);
        this.addToHead(node);
    };

    clearExpired() {
        const now = Date.now();

        let currentNode = this.tail;

        while(currentNode) {
            const prevNode = currentNode.prev;

            if(currentNode.expiredTime <= now) {
                this.cache.delete(currentNode.key);
                this.moveNode(node);
            };

            currentNode = prevNode;
        };
    };

    get(key) {
        const node = this.cache.get(key);
        const now = Date.now();

        if(!node) {
            return -1;
        };

        if(node.expiredTime <= now) {
            this.cache.delete(node.key);
            this.moveNode(node);

            return -1;
        };

        this.moveNodeToHead(node);

        return node.value;
    };

    put(key,value,ttl) {
        const now = Date.now();

        this.clearExpired();

        const oldNode = this.cache.get(key);

        if(oldNode) {
            oldNode.expiredTime = now + ttl;
            oldNode.value = value;

            this.moveNodeToHead(oldNode);
        }else{
            const newNode = this.createNode(key,value,ttl);
            this.cache.set(key,newNode);
            this.addToHead(newNode);
        };

        while(this.cache.size > this.capacity) {
            const node = this.tail;

            this.cache.delete(node.key);
            this.moveNode(node);
        };
    };
 };

// 示例测试用例
const cache = new LRUCache2(2);
cache.put('a', 1, 1000);
cache.put('b', 2, 1000);
console.log(cache.get('a')); // 输出 1

cache.put('c', 3, 1000); // 容量2，淘汰最少使用的b
console.log(cache.get('b')); // 输出 -1