How do you design an LRU cache?

The cache must support get and put in O(1). A hash map alone gives lookup but not ordering. A linked list alone gives ordering but not lookup. Together, the map stores node references and the list maintains recency order.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

The classic linked-list version

• Use a dummy head and tail to avoid null checks at the boundaries
• The map key points to the linked-list node
• On get, unlink the node and insert it at the front
• On put, update or create a node at the front
• When over capacity, remove the node before the tail and delete its map entry

The Map-based implementation is concise and correct for JavaScript interviews. The linked-list version is what interviewers usually mean when they ask you to design the structure from scratch, because it demonstrates pointer manipulation and explicit O(1) reasoning.