LRUCache.js

'use strict'

/// Circular double-linked list 
class Node {
  constructor () {
    this.key = null
    this.val = null
    this.prev = this
    this.next = this
  }

  linkTo (that) {
    this.next = that
    that.prev = this
  }

  insertBefore (that) {
    if (this.next !== that) {
      this.prev.linkTo(this.next)
      that.prev.linkTo(this)
      this.linkTo(that)
    }
  }
}

export class LRUCache {
  constructor (capacity) {
    this._capacity = capacity
    this._map = new Map() // key -> node
    this._end = new Node() // dummy head/tail
  }

  has (key) {
    const node = this._map.get(key)
    if (node) {
      node.insertBefore(this._end)
      return true
    }
    return false
  }

  get (key) {
    const node = this._map.get(key)
    if (node) {
      node.insertBefore(this._end)
      return node.val
    }
    return undefined
  }

  set (key, val) {
    let node = this._map.get(key)
    if (!node) {
      if (this._map.size >= this._capacity) {
        node = this._end.next
        this._map.delete(node.key)
      } else {
        node = new Node()
      }
      node.key = key
      this._map.set(key, node)
    }
    node.insertBefore(this._end)
    node.val = val
    return this
  }

  delete (key) {
    const node = this._map.get(key)
    if (node) {
      node.prev.linkTo(node.next)
      this._map.delete(key)
      return true
    }
    return false
  }

  clear () {
    this._map.clear()
    this._end.linkTo(this._end)
  }
  
  // Mostly useful for checking entries in LRU order in tests
  toArray () {
    const arr = []
    
    for (let node = this._end.next; node !== this._end; node = node.next) {
      arr.push([ node.key, node.val ])
    }
    
    return arr
  }
}