146.lru-cache.js

/**
 *
 * Node
 *
 * @param {*} key
 * @param {*} value
 * @param {Node} [next=null]
 * @param {Node} [prev=null]
 */
function Node(key, value, next = null, prev = null) {
  this.key = key;
  this.value = value;
  this.next = next;
  this.prev = prev;
}

/**
 *
 * LRUCache
 *
 * @param {number} capacity
 */

function LRUCache(capacity) {
  this.map = new Map();
  this.head = null;
  this.tail = null;
  this.size = 0;
  this.capacity = capacity;
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  if (this.map.has(key))  {

    this.remove(this.map.get(key));
    this.add(this.map.get(key));
    return this.map.get(key).value;
  } else {
    return -1;
  }
};

/**
 * @param {number} key
 * @param {number} value
 */
LRUCache.prototype.put = function(key, value) {
  if (this.map.has(key)) {
    const node = this.map.get(key);
    node.value = value;
    this.remove(node);
    this.add(node);
  } else {
    if (this.size >= this.capacity) {
      this.map.delete(this.tail.key);
      this.remove(this.tail);
    }
    this.map.set(key, new Node(key, value));
    this.add(this.map.get(key));
  }
};

/**
 * add
 *
 * @private
 * @param {Node} node
 *
 */
LRUCache.prototype.add = function (node) {
  if (this.size === 0) {
    this.head = node;
    this.tail = node;
  } else {
    this.head.prev = node;
    node.next = this.head;
    this.head = node;
  }
  this.size += 1;
};

/**
 * remove
 *
 * @private
 * @param {Node} node
 */
LRUCache.prototype.remove = function (node) {
  if ( node === this.head ) {
    this.head = this.head.next;
    if ( this.head !== null ) {
      this.head.prev = null;
    }
  } else if ( node === this.tail ) {
    this.tail = this.tail.prev;
    this.tail.next = null;
  } else {
    node.next.prev = node.prev;
    node.prev.next = node.next;
    node.next = null;
    node.prev = null;
  }
  this.size -= 1;
};

LRUCache.prototype.forEach = function(fn) {
	let node = this.head;
  let counter = 0;
  while (node) {
  	fn(node, counter);
    node = node.next;
    counter++;
	}
}

LRUCache.prototype[Symbol.iterator] = function*() {
  let node = this.head;
  while (node) {
  	yield node;
    node = node.next;
  }
}