146. LRU Cache

To achieve O(1) time for both GET and PUT, hash tables are the only thing you can think of. Every time you get/put, you put the node to the head of the linked list. At the same time, the node’s original prev and next can be connected, so the linked list must be a bidirectional list. The difficulty of code implementation is to deal with boundary cases, i.e. how to deal with the corresponding node when prev or next is null, and how to deal with head and tail when head and tail are null. We can draw all of this on a piece of paper to help us think more clearly when we’re writing code.

class LinkNode {
    key: number;
    val: number;
    prev: LinkNode;
    next: LinkNode;
    constructor(key:number, val:number) {
        this.key = key;
        this.val = val;
        this.prev = this.next = null; }};class LRUCache {
    head: LinkNode | null;
    tail: LinkNode | null;
    cap: number;
    key_node: Map<number,LinkNode>;
    constructor(capacity: number) {
        this.cap = capacity;
        this.key_node = new Map(a);this.head = this.tail = null;
    }

    get(key: number) :number {
        if (this.key_node.has(key)) {
            let node = this.key_node.get(key);
            let prev = node.prev, next = node.next;
            if (prev) {
                prev.next = next;
                node.prev = null;
                node.next = this.head;
                this.head.prev = node;
                this.head = node;
                if(! next)this.tail = prev;
                else next.prev = prev;
            }
            return node.val;
        } else return -1;
    }

    put(key: number.value: number) :void {
        if (this.key_node.has(key)) {
            let node = this.key_node.get(key);
            node.val = value;
            let prev = node.prev, next = node.next;
            if (prev) {
                prev.next = next;
                node.next = this.head;
                node.prev = null;
                this.head.prev = node;
                this.head = node;
                if(! next)this.tail = prev;
                elsenext.prev = prev; }}else {
            if (this.key_node.size == this.cap) {
                let node_toRemove = this.tail;
                this.key_node.delete(node_toRemove.key);
                this.tail = node_toRemove.prev;
                if (this.tail) this.tail.next = null;
                if (this.head.key == node_toRemove.key) this.head = null;
            }
            let node = new LinkNode(key, value);
            this.key_node.set(key, node);
            if (this.head) {
                node.next = this.head;
                this.head.prev = node;
                this.head = node;
            } else {
                this.head = this.tail = node; }}}}Copy the code