定义节点

class Node {
    constructor(prev, next, key, value){
        this.prev = prev
        this.next = next
        this.value = value
        this.key = key
    }
}

LRU算法

class LRU {
    constructor(limit){
        this.map = new Map()
        this.head = null
        this.tail = null
        this.limit = limit
    }
    // 如果存在,移动到队尾
    get(key){
        let node = this.map.get(key)
        if(!node){
            return null
        }else{ 
            this.moveToTail(node)
            this.showChain()
            return node.value
        }
    }
    // 节点移动到队尾
    moveToTail(node){
        // 本身在队列队尾，不做操作
        if(node.next === null){
            return
        }
        // 本身在队首，移动到队尾，更新head
        if(node.prev === null){
            this.head = node.next
            this.tail.next = node
            this.tail = node
            node.next = null
        }
        // 在中间
        node.prev.next = node.next
        node.next.prev = node.prev
        this.tail.next = node
        node.prev = this.tail
        this.tail = this.tail.next
        this.tail.next = null
    }
    // 插入节点
    put(key, value){
        let node = new Node(null, null, key, value)
        this.map.set(key, node)
        this.moveToTail(node)
        if(!this.head && !this.tail){
            this.head = node
            this.tail = node
        }else{
            this.tail.next = node
            node.prev = this.tail
            this.tail = this.tail.next
        }
        // 超过缓存区大小 
        if(this.limit < this.map.size){
            let headNode = this.head
            this.head = this.head.next
            this.head.prev = null
            this.map.delete(headNode.key)
            headNode = null
        } 
        this.showChain()
    }
      // 打印辅助函数
    showChain(){
        let str = ''
        let head = this.head
        let tail = this.tail
        while(head){
            str += head.value + '->'
            head = head.next
        }
        str += "\n tail: "
        while(tail){
            str += tail.value + '->'
            tail = tail.prev
        }
        console.log("chain:", str)
    }
}

测试用例

let lru = new LRU(5)
console.log(lru.get(1));
for (let i = 0; i < 6; i++) {
    lru.put(i,i)
}
console.log(lru.get(0));
console.log(lru.get(2));
console.log(lru.get(3));
console.log(lru.get(4));
console.log(lru.get(5));