Building an LRU Cache in TypeScript: Hash Map and Doubly Linked List in Practice

LRU Cache is one of those LeetCode problems that is much more interesting than its interface suggests. At first glance, it looks as if we are only being asked to implement two methods:

• get
• put

That sounds simple enough. The catch is the eviction rule and the performance requirement. We need to remove the least recently used item when the cache is full, and we need both operations to stay O(1).

That combination is what makes the problem worth writing about. It is not a map problem. It is not a linked‑list problem. It is the coordination problem between the two.

What the Cache Needs to Remember

An LRU cache has to answer two different questions quickly:

1. Given a key, where is its value?
2. Which key was used least recently?

Those are not the same lookup.

A hash map is excellent for the first one:

• key to node lookup in constant time

A doubly linked list is excellent for the second one:

• keep items ordered from most recently used to least recently used
• evict from the tail in constant time

That pairing is the whole design.

The Naive Approach and Where It Falls Down

We could store entries in a map and keep an array of usage order beside it. On every get, move the key to the front. On eviction, remove the oldest key.

That works functionally. The problem is movement cost. Removing a key from the middle of an array or unshifting a new one into the front is not reliably O(1).

The problem is not lookup. It is reordering.

A Surprisingly Practical TypeScript Alternative

Before getting to the classic interview answer, it is worth saying something slightly awkward: in JavaScript and TypeScript, a plain Map can already behave a lot like an LRU cache because insertion order is preserved.

That means we can:

• delete and reinsert a key to mark it as recent
• evict the first key when capacity is exceeded

export class LRUCache {
  private readonly entries = new Map<number, number>();

  public constructor(private readonly capacity: number) {}

  public get(key: number): number {
    const value = this.entries.get(key);

    if (value === undefined) {
      return -1;
    }

    this.entries.delete(key);
    this.entries.set(key, value);

    return value;
  }

  public put(key: number, value: number): void {
    if (this.entries.has(key)) {
      this.entries.delete(key);
    }

    this.entries.set(key, value);

    if (this.entries.size > this.capacity) {
      const oldestKey = this.entries.keys().next().value;

      if (oldestKey !== undefined) {
        this.entries.delete(oldestKey);
      }
    }
  }
}

Honestly, for day‑to‑day TypeScript application code, that is often the version I would reach for first.

Why That Still is Not the Real Algorithm Lesson

The reason people keep teaching LRU as hash map plus doubly linked list is not because the Map version is fake. It is because the linked‑list version explains the real mechanism without leaning on a built‑in container's ordering behaviour.

That matters if:

• the interview expects the classic data‑structure answer
• the language does not give you an ordered hash map so conveniently
• you want to understand why the O(1) claim is structurally true

So the Map‑only version is practical. The map‑plus‑list version is the better algorithm article.

The Core Invariant

Once we switch to the classic structure, the cache becomes much easier to reason about if we keep one rule in view:

• the linked list is always ordered from most recently used to least recently used

That means:

• when a key is read, its node moves to the front
• when a key is updated, its node moves to the front
• when a new key is inserted, its node goes to the front
• when capacity is exceeded, we evict from the back

The map simply tells us where the node for a given key currently lives.

A Practical Hash Map plus Doubly Linked List Implementation

type CacheNode = {
  key: number;
  value: number;
  prev: CacheNode | null;
  next: CacheNode | null;
};

export class LRUCache {
  private readonly nodes = new Map<number, CacheNode>();
  private readonly head: CacheNode = {
    key: 0,
    value: 0,
    prev: null,
    next: null,
  };
  private readonly tail: CacheNode = {
    key: 0,
    value: 0,
    prev: null,
    next: null,
  };

  public constructor(private readonly capacity: number) {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  public get(key: number): number {
    const node = this.nodes.get(key);

    if (!node) {
      return -1;
    }

    this.moveToFront(node);

    return node.value;
  }

  public put(key: number, value: number): void {
    const existingNode = this.nodes.get(key);

    if (existingNode) {
      existingNode.value = value;
      this.moveToFront(existingNode);
      return;
    }

    const node: CacheNode = {
      key,
      value,
      prev: null,
      next: null,
    };

    this.nodes.set(key, node);
    this.insertAfterHead(node);

    if (this.nodes.size > this.capacity) {
      this.evictLeastRecent();
    }
  }

  private moveToFront(node: CacheNode): void {
    this.removeNode(node);
    this.insertAfterHead(node);
  }

  private insertAfterHead(node: CacheNode): void {
    const firstRealNode = this.head.next;

    node.prev = this.head;
    node.next = firstRealNode;
    this.head.next = node;

    if (firstRealNode) {
      firstRealNode.prev = node;
    }
  }

  private removeNode(node: CacheNode): void {
    const previousNode = node.prev;
    const nextNode = node.next;

    if (previousNode) {
      previousNode.next = nextNode;
    }

    if (nextNode) {
      nextNode.prev = previousNode;
    }
  }

  private evictLeastRecent(): void {
    const nodeToRemove = this.tail.prev;

    if (!nodeToRemove || nodeToRemove === this.head) {
      return;
    }

    this.removeNode(nodeToRemove);
    this.nodes.delete(nodeToRemove.key);
  }
}

Why the Sentinel Nodes are Worth It

The dummy head and tail nodes are not storing real cache data. They are there to make the pointer operations much calmer.

Without them, we would need more edge‑case branching for:

• empty list
• single‑item list
• moving the first or last real node

With sentinels, every real node always sits between two neighbours, even if one of those neighbours is a dummy boundary node. That makes removeNode and insertAfterHead much more mechanical.

How the Two Data Structures Cooperate

This is the part that actually matters.

When we call get(key):

• the map tells us whether the key exists
• if it does, it returns the node immediately
• the list then moves that node to the front because it is now the most recently used

When we call put(key, value):

• if the key exists already, update and move it to the front
• if the key is new, create a node, add it to the map, insert it at the front
• if capacity is now exceeded, remove the node at the tail end and delete its key from the map

So the map handles:

• direct addressability

and the list handles:

• recency ordering

Neither one can do the full job alone.

Which Solution is Best?

For real TypeScript application work, I think the ordered‑Map version is often the best answer if:

• the environment guarantees Map insertion order
• the workload is modest
• readability matters more than demonstrating the underlying mechanics

For LeetCode, technical interviews, and cross‑language data‑structure thinking, the hash map plus doubly linked list version is the best answer. It is more explicit, more portable, and more honest about where the constant‑time guarantees come from.

So my answer is a split one again:

• best practical TypeScript shortcut: ordered Map
• best algorithm answer: hash map plus doubly linked list

Why a Singly Linked List is Awkward Here

It is worth saying what the doubly linked list is buying us. If the list were singly linked, removing an arbitrary node would require us to know its predecessor first.

That is a problem, because the map gives us the node itself, not the node before it.

With prev and next, a node can remove itself from the list in constant time once we already have its reference. That is exactly what moveToFront depends on.

Common Mistakes

Updating the Map but Forgetting the List

Then the cache returns correct values but evicts the wrong entry later.

Moving Nodes by Creating New Ones Unnecessarily

That can work, but it complicates the map and makes the coordination messier than it needs to be.

Not Deleting the Evicted Key from the Map

That leaves stale references behind and breaks lookups.

Treating Eviction as "Remove Oldest Inserted"

LRU means least recently used, not least recently created. Reads count too.

The Broader Lesson

LRU Cache is a strong design problem because it shows how often good data‑structure answers are really hybrids. One container solves one access pattern. Another solves a different one. The actual solution is the disciplined connection between them.

That is a pattern worth noticing well beyond interviews. A lot of systems work is really about asking:

• what needs to be fast?
• what order needs to be preserved?
• which structure answers which question?

The Part Worth Carrying Forward

• A map alone solves key lookup, not recency ordering.
• A linked list alone solves ordering, not direct lookup.
• The classic LRU answer works because the map and doubly linked list are doing different jobs in constant time.

This problem is satisfying because the final design is not arbitrary. Every piece is there because one operation needs it.