Skip to content
The Chat Archive
o4-mini-2025-04-16· OpenAI LMArena Human Preference 140K

Can you write me a typescript class that handles LRU cache

  1. User

    Can you write me a typescript class that handles LRU cache

  2. Assistant

    Here’s a fully‐typed, generic LRU Cache implementation in TypeScript. It uses a doubly‐linked list + a Map to achieve O(1) get and put operations.

    /**
     * A node in the doubly linked list
     */
    class DLLNode<K, V> {
      key: K
      value: V
      prev: DLLNode<K, V> | null = null
      next: DLLNode<K, V> | null = null
    
      constructor(key: K, value: V) {
        this.key = key
        this.value = value
      }
    }
    
    /**
     * LRU Cache Class
     */
    export class LRUCache<K, V> {
      private capacity: number
      private map: Map<K, DLLNode<K, V>> = new Map()
      private head: DLLNode<K, V> | null = null
      private tail: DLLNode<K, V> | null = null
    
      /**
       * @param capacity maximum number of items in cache
       */
      constructor(capacity: number) {
        if (capacity <= 0) {
          throw new Error("Capacity must be greater than 0")
        }
        this.capacity = capacity
      }
    
      /**
       * Get value by key. Marks node as most‐recently used.
       */
      get(key: K): V | undefined {
        const node = this.map.get(key)
        if (!node) return undefined
    
        // Move the accessed node to head (MRU)
        this.moveToHead(node)
        return node.value
      }
    
      /**
       * Insert or update value by key. 
       * If full, evicts least‐recently used.
       */
      put(key: K, value: V): void {
        const node = this.map.get(key)
        if (node) {
          // Update and move to head
          node.value = value
          this.moveToHead(node)
        } else {
          // New node
          const newNode = new DLLNode(key, value)
          if (this.map.size >= this.capacity) {
            this.evictLRU()
          }
          this.addNode(newNode)
          this.map.set(key, newNode)
        }
      }
    
      /**
       * Remove an item by key
       */
      delete(key: K): boolean {
        const node = this.map.get(key)
        if (!node) return false
        this.removeNode(node)
        this.map.delete(key)
        return true
      }
    
      /**
       * Clear entire cache
       */
      clear(): void {
        this.head = this.tail = null
        this.map.clear()
      }
    
      // ----- Internal helpers -----
    
      /** Remove a node from the list */
      private removeNode(node: DLLNode<K, V>) {
        const { prev, next } = node
    
        if (prev) prev.next = next
        else this.head = next
    
        if (next) next.prev = prev
        else this.tail = prev
    
        node.prev = node.next = null
      }
    
      /** Add node right after head */
      private addNode(node: DLLNode<K, V>) {
        if (!this.head) {
          this.head = this.tail = node
        } else {
          node.next = this.head
          this.head.prev = node
          this.head = node
        }
      }
    
      /** Move an existing node to head (MRU) */
      private moveToHead(node: DLLNode<K, V>) {
        if (node === this.head) return
        this.removeNode(node)
        this.addNode(node)
      }
    
      /** Evict least‐recently used node (tail) */
      private evictLRU() {
        if (!this.tail) return
        const lruKey = this.tail.key
        this.removeNode(this.tail)
        this.map.delete(lruKey)
      }
    }
    

    Usage Example:

    const cache = new LRUCache<string, number>(3)
    
    cache.put("a", 1)
    cache.put("b", 2)
    cache.put("c", 3)
    
    cache.get("a")    // 1, order is now a→c→b (a is MRU)
    cache.put("d", 4) // evicts "b" (LRU)
    
    console.log(cache.get("b")) // undefined
    console.log(cache.get("c")) // 3
    

    Time Complexity

    • get: O(1)
    • put: O(1)

    Feel free to tweak or extend (e.g. add stats, async hooks, etc.). 🚀

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.