liveBook · Manning

Doubly linked list

As explained in Acing the Frontend Interview

A doubly linked list is a linked sequence whose nodes contain references to both their preceding and succeeding nodes.

A doubly linked list stores a sequence of nodes, with each node referencing both its predecessor and successor. In an LRU cache, it tracks access order: the head identifies the most recently used item, while the tail identifies the least recently used item. section 6.4

Interview scenario

When designing a high-throughput API cache, explain how the list supports eviction and what happens under concurrent access. Multiple threads may reposition or remove nodes simultaneously, causing stale reads or corrupted ordering. Discuss locking, lock-free structures, or sharding as synchronization trade-offs. section 6.4

Listing 6.6 LRU cache implementation in TypeScript
class LRUCache<K, V> {
  private cache: Map<K, V>;
  private capacity: number;
   constructor(capacity: number) {
    if (capacity <= 0) {
      throw new Error('Capacity must be greater than 0');
    }
    this.capacity = capacity; #A
    this.cache = new Map(); #B
  }
  get(key: K): V | -1 { #C
    if (!this.cache.has(key)) { #D
      return -1;
    }
    const value = this.cache.get(key)!; #E
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }
  put(key: K, value: V): void { #F
    if (this.cache.has(key)) {
      this.cache.delete(key); #G
    }
    this.cache.set(key, value); #H
    if (this.cache.size > this.capacity) {
      const lruKey = this.cache.keys().next().value!; #I
      this.cache.delete(lruKey); #J
    }
  }
  entries(): [K, V][] { #K
    return Array.from(this.cache.entries());
  }
}

Use the TypeScript LRU implementation to connect access-order updates, capacity checks, and least-recently-used removal to the data structure’s cache role. section 6.4

How Acing the Frontend Interview covers it

How deep it goes
Explains cache-order tracking and concurrency hazards but stops short of a standalone node-level implementation.
Examples
Uses a high-throughput API cache, head-and-tail access order, and sharded caches with Redis fallback.
What you can do after
Evaluate cache designs by explaining eviction order, concurrent mutation risks, and synchronization trade-offs.
How it connects
Connects doubly linked lists with LRU caches, hash maps, eviction policies, concurrency, and sharded caches.

Also explained in

Compare how 4 books explain doubly linked list →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Acing the Frontend Interview. The section links point to the parts of the book it draws on.