LRU (Least Recently Used) Cache

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.order = new DoublyLinkedList();
  }
  
  get(key) {
    if (!this.cache.has(key)) {
      return undefined;
    }
    
    const node = this.cache.get(key);
    // Move to front (most recently used)
    this.order.moveToFront(node);
    return node.value.value;
  }
  
  put(key, value) {
    if (this.cache.has(key)) {
      // Update existing
      const node = this.cache.get(key);
      node.value.value = value;
      this.order.moveToFront(node);
      return;
    }
    
    if (this.cache.size >= this.capacity) {
      // Remove least recently used
      const lruNode = this.order.removeTail();
      if (lruNode) {
        this.cache.delete(lruNode.value.key);
      }
    }
    
    // Add new node
    const newNode = this.order.addToFront({ key, value });
    this.cache.set(key, newNode);
  }
  
  delete(key) {
    if (!this.cache.has(key)) {
      return false;
    }
    
    const node = this.cache.get(key);
    this.order.removeNode(node);
    this.cache.delete(key);
    return true;
  }
  
  clear() {
    this.cache.clear();
    this.order = new DoublyLinkedList();
  }
  
  has(key) {
    return this.cache.has(key);
  }
  
  keys() {
    const keys = [];
    let current = this.order.head;
    while (current) {
      keys.push(current.value.key);
      current = current.next;
    }
    return keys;
  }
  
  values() {
    const values = [];
    let current = this.order.head;
    while (current) {
      values.push(current.value.value);
      current = current.next;
    }
    return values;
  }
  
  entries() {
    const entries = [];
    let current = this.order.head;
    while (current) {
      entries.push([current.value.key, current.value.value]);
      current = current.next;
    }
    return entries;
  }
  
  getSize() {
    return this.cache.size;
  }
  
  getCapacity() {
    return this.capacity;
  }
}

// Doubly Linked List for LRU ordering
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  addToFront(value) {
    const newNode = new ListNode(value);
    
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    
    this.size++;
    return newNode;
  }
  
  moveToFront(node) {
    if (node === this.head) {
      return;
    }
    
    this.removeNode(node);
    this.addNodeToFront(node);
  }
  
  addNodeToFront(node) {
    node.prev = null;
    node.next = this.head;
    
    if (this.head) {
      this.head.prev = node;
    }
    
    this.head = node;
    
    if (!this.tail) {
      this.tail = node;
    }
    
    this.size++;
  }
  
  removeNode(node) {
    if (node.prev) {
      node.prev.next = node.next;
    } else {
      this.head = node.next;
    }
    
    if (node.next) {
      node.next.prev = node.prev;
    } else {
      this.tail = node.prev;
    }
    
    node.prev = null;
    node.next = null;
    this.size--;
    return node;
  }
  
  removeTail() {
    if (!this.tail) {
      return null;
    }
    
    return this.removeNode(this.tail);
  }
}

class ListNode {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}