LRU.js

var LRUCache = function(capacity) {
  // beofre <--> { k0, v0 } <--> { k1, v1 }
  const map = {}; // map key to node
  const before = {};
  let count = 0;
  let tail = before;
  
  return { get, put };
  
  function get(k) {
    if (!map[k]) return -1;
    if (map[k] === tail) return tail.val;
    
    const curr = map[k];
    const left = curr.left;
    const right = curr.right;
    left.right = right;
    right.left = left;

    tail.right = curr;
    curr.left = tail;

    tail = curr;
    tail.right = null;
    return tail.val;
  }

  function put(k, v) {
    if (map[k] !== undefined) {
      map[k].val = v;
    } else if (count === capacity) {
      delete map[before.right.key];
      map[k] = before.right;
      map[k].key = k;
      map[k].val = v;
    } else {
      tail.right = { val: v, key: k, left: tail };
      tail = tail.right;
      map[k] = tail;
      count++;
    }
    get(k);
  }
};