In-memory LRU cache

lru-cache.ts

type Node<K, V> = {
  key: K
  value: V
  previous: Node<K, V> | null
  next: Node<K, V> | null
}

export class InMemoryLru<Key, Value = unknown> {
  private readonly capacity: number
  private readonly map = new Map<Key, Node<Key, Value>>()

  // Dummy sentinels to avoid null checks when linking
  private readonly head: Node<Key, Value> = {
    key: null as any,
    value: null as any,
    previous: null,
    next: null,
  }
  private readonly tail: Node<Key, Value> = {
    key: null as any,
    value: null as any,
    previous: null,
    next: null,
  }

  constructor(capacity = 4096) {
    if (capacity <= 0) throw new Error('capacity must be > 0')
    this.capacity = capacity
    this.head.next = this.tail
    this.tail.previous = this.head
  }

  // --- list helpers (no Map ops here) ---
  #addToFront(node: Node<Key, Value>): void {
    node.previous = this.head
    node.next = this.head.next!
    this.head.next!.previous = node
    this.head.next = node
  }

  #removeNode(node: Node<Key, Value>): void {
    node.previous!.next = node.next!
    node.next!.previous = node.previous!
    node.previous = node.next = null
  }

  #moveToFront(node: Node<Key, Value>): void {
    this.#removeNode(node)
    this.#addToFront(node)
  }

  #popLeastRecentlyUsed(): Node<Key, Value> | null {
    const node = this.tail.previous!
    if (node === this.head) return null
    this.#removeNode(node)
    return node
  }

  // --- API ---
  public get(key: Key): Value | undefined {
    const node = this.map.get(key) // 1 hash
    if (!node) return undefined

    this.#moveToFront(node) // 0 hashes, just pointers
    return node.value
  }

  public set(key: Key, value: Value): void {
    const existing = this.map.get(key) // 1 hash
    if (existing) {
      existing.value = value
      this.#moveToFront(existing) // 0 hashes
      return
    }

    const node: Node<Key, Value> = { key, value, previous: null, next: null }
    this.map.set(key, node) // 1 hash (amortized for new keys)
    this.#addToFront(node)

    if (this.map.size > this.capacity) {
      const lru = this.#popLeastRecentlyUsed()
      if (lru) this.map.delete(lru.key) // +1 hash only when evicting
    }
  }

  public delete(key: Key): void {
    const node = this.map.get(key) // 1 hash
    if (!node) return
    this.#removeNode(node) // 0 hashes
    this.map.delete(key) // +1 hash
  }

  public has(key: Key): boolean {
    return this.map.has(key)
  }

  public get size(): number {
    return this.map.size
  }

  public clear(): void {
    this.map.clear()
    this.head.next = this.tail
    this.tail.previous = this.head
  }
}

export const lru = new InMemoryLru<string, string>()

lru.set('key', 'value')
console.log(lru.get('key'))
console.log(lru.size)
console.log(lru.has('key'))
console.log(lru.clear())
console.log(lru.size)
console.log(lru.has('key'))