LRU算法

// 双向链表节点 
class LinkNode {
    public val: number;
    public key: number;
    public next: LinkNode | null;
    public front: LinkNode | null;
    constructor(key: number, val: number) {
        this.key = key;
        this.val = val;
    }
}
class LRUCache {
    public capacity: number; // 最大数量限制
    public map: Map<number, LinkNode>; // 
    public head: LinkNode;
    public tail: LinkNode;
    constructor(capacity: number) {
        this.capacity = capacity;
        this.head = new LinkNode(0, 0);
        this.tail = new LinkNode(0, 0);
        this.map = new Map();
          // 默认head.next指向tail tail.front指向head
        this.head.next = this.tail;
        this.tail.front = this.head;
    }
      // 删除最后一个节点
    deleteLastNode(): void {
        const lastNode = this.tail.front;
        lastNode.front.next = this.tail;
        this.tail.front = lastNode.front;
        this.map.delete(lastNode.key);
    }
      // 移动节点到最前面 
    moveNodeToTop(node: LinkNode): void {
        node.front.next = node.next;
        node.next.front = node.front;
        const temp = this.head.next;
        temp.front = node;
        node.next = temp;
        node.front = this.head;
        this.head.next = node;
    }
    get(key: number): number {
        if (this.map.has(key)) {
            const node = this.map.get(key);
            this.moveNodeToTop(node);
            return node.val;
        }
        return -1;
    }
    put(key: number, value: number): void {
        if (!this.map.has(key)) {
            if (this.map.size === this.capacity) {
                this.deleteLastNode();
            }
            const temp = this.head.next;
            const newNode = new LinkNode(key, value);
            this.head.next = newNode;
            newNode.front = this.head;
            newNode.next = temp;
            temp.front = newNode;
            this.map.set(key, newNode);
        } else {
            const node = this.map.get(key);
            node.val = value;
            this.moveNodeToTop(node);
        }
    }
}