https://leetcode.com/problems/lru-cache/

LRUCache.js

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.size = 0;
    this.capacity = capacity;
    this.index = new Map(); // <key: ListNode>

    this.head = new ListNode(null, null);
    this.tail = new ListNode(null, null);
    this.head.prev = this.tail;
    this.tail.next = this.head;
};

function ListNode(val, key){
    this.val = val;
    this.key = key;
    this.next = null;
    this.prev = null;
}

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(!this.index.has(key)) return -1;
    const value = this.index.get(key).val;
    this.put(key, value);
    return value;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.index.has(key)){ // if this key already exists
        // remove keyed item from wherever it is
        const nodeToEvict = this.index.get(key);
        nodeToEvict.next.prev = nodeToEvict.prev;
        nodeToEvict.prev.next = nodeToEvict.next;
        this.index.delete(key);
    }else if(this.size === this.capacity){ // if we're at capacity
        // evict item at tail
        const nodeToEvict = this.tail.next;
        const keyToEvict = nodeToEvict.key;
        this.tail.next = nodeToEvict.next;
        nodeToEvict.next.prev = this.tail;
        this.index.delete(keyToEvict);
    }else{
        this.size++;
    }
    // insert item at head
    const newNode = new ListNode(value, key);
    
    newNode.next = this.head;
    newNode.prev = this.head.prev;
    this.head.prev.next = newNode;
    this.head.prev = newNode;
    
    this.index.set(key, newNode);
};

/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */