LruCache doodle

LruCache.js

console.clear()

class ListNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.next = null
    this.previous = null
  }
  
  toString() {
    if (this === this.next) {
      return `{${this.key}: ${this.value}}->self`
    }
    if (this === (this.next || {}).next) {
      return `{${this.key}: ${this.value}}->{${this.next.key}: ${this.next.value}}->self`
    }
    const connection = this === (this.next ? this.next.previous : null) ? '<->' : '->'
    const next = this.next ? `${connection}${this.next.toString()}` : ''
    return `{${this.key}: ${this.value}}${next}`
  }
}

class LruCache {
  constructor(maxSize) {
    this.maxSize = maxSize
    this.mostRecentlyAccessed = null
    this.leastRecentlyAccessed = null
    this.cache = {}
    this.cacheSize = 0
  }
  
  put(key, value) {
    const node = new ListNode(key, value)
    this.cache[key] = node
    this.cacheSize += 1
    
    if (this.mostRecentlyAccessed === null && this.leastRecentlyAccessed === null) {
      this.mostRecentlyAccessed = node
      this.leastRecentlyAccessed = node
      return
    }
    
    this.mostRecentlyAccessed.next = node
    node.previous = this.mostRecentlyAccessed
    this.mostRecentlyAccessed = node
    
    if (this.cacheSize > this.maxSize) {
      // remove least recently accessed
      delete this.cache[this.leastRecentlyAccessed.key]
      this.leastRecentlyAccessed = this.leastRecentlyAccessed.next
      this.leastRecentlyAccessed.previous = null
    }
  }
  
  get(key) {
    const node = this.cache[key]
    
    if (node === undefined) {
      return
    }
    
    if (node.previous !== null) {
      node.previous.next = node.next
    }
    
    if (node.next !== null) {
      node.next.previous = node.previous
    }
    
    if (node === this.leastRecentlyAccessed) {
      this.leastRecentlyAccessed = node.next
    }
    
    node.next = null
    node.previous = this.mostRecentlyAccessed
    this.mostRecentlyAccessed.next = node
    this.mostRecentlyAccessed = node
    
    return node
  }
}

const cache1 = new LruCache(2)
cache1.put(1, "1")
console.log(cache1.mostRecentlyAccessed.toString(), cache1.leastRecentlyAccessed.toString())
cache1.put(2, "2")
console.log(cache1.mostRecentlyAccessed.toString(), cache1.leastRecentlyAccessed.toString())
cache1.get(1)
console.log(cache1.mostRecentlyAccessed.toString(), cache1.leastRecentlyAccessed.toString())
cache1.put(3, "3")
console.log(cache1.mostRecentlyAccessed.toString(), cache1.leastRecentlyAccessed.toString())

const cache2 = new LruCache(5)
cache2.put(1, "one")
cache2.put(2, "two")
cache2.put(3, "three")
//cache2.put("four", 4)
cache2.put({ foo: 'bar' }, "omg")
cache2.put(5, "five")
cache2.get(1)
cache2.put(6, "six")

console.log(cache2.cache) // Object { 1:ListNode, 3:ListNode, 5:ListNode, 6:ListNode, [object Object]:ListNode }
console.log(cache2.mostRecentlyAccessed.toString()) // {6: six}
console.log(cache2.leastRecentlyAccessed.toString()) // {3: three}<->{[object Object]: omg}<->{5: five}<->{1: one}<->{6: six}