Singly, Doubly, and Intrusive Linked Lists: Beyond the Whiteboard Interview

Everyone loves to hate on the Linked List once their software engineering interview is over. Yet your operating system kernel, React's reconciler, and your Redis caching cluster would collapse without it. Here is where Linked Lists actually shine in production.

---

Ask a room of mid-level software engineers when they last wrote a Linked List on the job, and you will likely hear a chorus of laughter: "Only on a whiteboard when the interviewer asked me to reverse one in place!"

After reading Article 1 on Contiguous Memory and Dynamic Arrays, it is easy to see why Linked Lists get a bad rap. Because each node in a linked list is allocated separately on the heap, traversing a list requires pointer chasing—jumping across scattered memory addresses that trigger CPU L1/L2 cache misses at nearly every step.

So why do university Computer Science departments still dedicate weeks of lecture and lab time to Singly, Doubly, Circular, and Intrusive Linked Lists?

Because when a system requires deterministic $O(1)$ splicing, constant-time removal of an已知 (known) node reference without shifting a single byte of adjacent memory, or dynamic reorganization of execution queues, contiguous arrays hit a brick wall—and Linked Lists become irreplaceable.

---

1. The Academic Foundation: Nodes, Pointers, and Structural Invariants

A Linked List is a linear collection of data elements, called Nodes, where linear order is not given by physical placement in RAM, but by explicit memory references (pointers) stored inside each node.

The Three Canonical Variants Taught in University

1. Singly Linked List (SLL): Each node stores a value payload and a single next pointer. Traversal is strictly unidirectional (head -> tail).
2. Doubly Linked List (DLL): Each node stores value, prev, and next pointers. Given a direct reference to any node in the list, you can unlink it or splice a new node before/after it in strict $O(1)$ worst-case time.
3. Sentinel (Dummy Head/Tail) Doubly Linked List: By anchoring the list between two permanent sentinel nodes (HEAD_SENTINEL and TAIL_SENTINEL), we eliminate every if (node === this.head) and if (node.next === null) null-check branch. In systems programming, eliminating conditional branches inside hot loops avoids CPU branch misprediction penalties.

flowchart LR
    subgraph SentinelDLL["Sentinel-Anchored Doubly Linked List (Zero Null-Check Branching)"]
        direction LR
        H["HEAD SENTINEL<br/>(prev: null)"] <-->|"next / prev"| N1["Node A<br/>Key: 'user:101'"]
        N1 <-->|"next / prev"| N2["Node B<br/>Key: 'user:204'"]
        N2 <-->|"next / prev"| N3["Node C<br/>Key: 'user:309'"]
        N3 <-->|"next / prev"| T["TAIL SENTINEL<br/>(next: null)"]
    end

The Pointer Splice Operation ($O(1)$ Exact)

Consider what happens when we remove Node B from the middle of a 10-million-element Doubly Linked List when we already hold a reference to Node B:

flowchart TD
    Step1["1. Locate Target Node B via Direct Reference O(1)"] --> Step2["2. Wire B.prev.next = B.next<br/>(Node A.next now points to Node C)"]
    Step2 --> Step3["3. Wire B.next.prev = B.prev<br/>(Node C.prev now points to Node A)"]
    Step3 --> Step4["4. Clear B.prev = null, B.next = null<br/>(Isolated for Garbage Collection in O(1))"]

Notice that whether the list holds $10$ nodes or $10,000,000$ nodes, literally four pointer assignments execute. Zero elements are shifted. Zero memory reallocations occur.

Complexity Comparison: Singly vs. Doubly Linked Lists

Operation	Singly Linked List	Doubly Linked List (with Sentinels)	Dynamic Array
Access by Index (get(i))	$O(n)$	$O(n)$	$O(1)$
Insert/Delete at Head	$O(1)$	$O(1)$	$O(n)$
Insert/Delete at Tail	$O(1)$ insert / $O(n)$ delete	$O(1)$ both	$O(1)$ amortized
Delete Given Node Reference	$O(n)$ (must find predecessor)	$O(1)$ exact	$O(n)$ (must shift tail)
Splice / Move Node to Front	$O(n)$	$O(1)$ exact	$O(n)$

---

2. The Production Powerhouse: Hash Map + Doubly Linked List = $O(1)$ LRU Cache

If you ask a senior backend architect where Doubly Linked Lists appear most often in distributed systems, the #1 answer is the LRU (Least Recently Used) Cache.

Wait—how do we overcome the Linked List's $O(n)$ lookup weakness while keeping its $O(1)$ node-reordering superpower? We fuse a Hash Map with a Doubly Linked List.

flowchart TB
    subgraph HashMap["Hash Map Index: O(1) Key -> Node Lookup"]
        K1["'session:a1'"]
        K2["'session:b2'"]
        K3["'session:c3'"]
    end

    subgraph DLL["Doubly Linked List: O(1) Recency Ordering (MRU -> LRU)"]
        direction LR
        Head["MRU Head"] <--> NodeB["Node: session:b2"]
        NodeB <--> NodeA["Node: session:a1"]
        NodeA <--> NodeC["Node: session:c3"]
        NodeC <--> Tail["LRU Tail"]
    end

    K1 -.->|"Direct Pointer"| NodeA
    K2 -.->|"Direct Pointer"| NodeB
    K3 -.->|"Direct Pointer"| NodeC

1. When a key is read via get(key), we look up its Node in the Hash Map in $O(1)$ time, detach that Node from its current position in the Doubly Linked List in $O(1)$ time, and re-attach it right after MRU Head in $O(1)$ time.
2. When the cache reaches full capacity and a new key is inserted via put(key, value), we evict Tail.prev (the Least Recently Used node) in $O(1)$ time and delete its key from the Hash Map.

---

3. Under the Hood: Testable Production LRU Cache & Cycle Detector

Below is a complete, zero-dependency TypeScript implementation of a Sentinel-Anchored Doubly Linked List powering an $O(1)$ LRU Cache, followed by Floyd's Tortoise and Hare Cycle Detection Algorithm ($O(n)$ time, $O(1)$ auxiliary space).

Copy and run this code directly in the JS/TS Playground:

/**
 * Doubly Linked List Node for O(1) Splicing
 */
class DListNode<K, V> {
  public key: K;
  public value: V;
  public prev: DListNode<K, V> | null = null;
  public next: DListNode<K, V> | null = null;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}

/**
 * Production-Grade O(1) LRU Cache backed by a Sentinel Doubly Linked List + Map
 */
class LRUCache<K, V> {
  private readonly capacity: number;
  private readonly index: Map<K, DListNode<K, V>>;
  private readonly headSentinel: DListNode<K, V>;
  private readonly tailSentinel: DListNode<K, V>;

  constructor(capacity: number) {
    if (capacity < 1 || !Number.isInteger(capacity)) {
      throw new RangeError("LRU Cache capacity must be a positive integer.");
    }
    this.capacity = capacity;
    this.index = new Map<K, DListNode<K, V>>();

    // Sentinel nodes eliminate all null-pointer edge cases during splice
    this.headSentinel = new DListNode<K, V>(undefined as unknown as K, undefined as unknown as V);
    this.tailSentinel = new DListNode<K, V>(undefined as unknown as K, undefined as unknown as V);
    this.headSentinel.next = this.tailSentinel;
    this.tailSentinel.prev = this.headSentinel;
  }

  public get size(): number {
    return this.index.size;
  }

  /**
   * O(1) Lookup + O(1) Promotion to Most Recently Used (MRU)
   */
  public get(key: K): V | undefined {
    const node = this.index.get(key);
    if (!node) {
      return undefined;
    }
    // Splice node out of current position and move to front (MRU)
    this.unlinkNode(node);
    this.attachAfterHead(node);
    return node.value;
  }

  /**
   * O(1) Upsert + O(1) Tail Eviction when over capacity
   */
  public put(key: K, value: V): void {
    const existing = this.index.get(key);
    if (existing) {
      existing.value = value;
      this.unlinkNode(existing);
      this.attachAfterHead(existing);
      return;
    }

    if (this.index.size >= this.capacity) {
      // Evict Least Recently Used node right before tailSentinel
      const lruNode = this.tailSentinel.prev!;
      this.unlinkNode(lruNode);
      this.index.delete(lruNode.key);
    }

    const newNode = new DListNode<K, V>(key, value);
    this.attachAfterHead(newNode);
    this.index.set(key, newNode);
  }

  /**
   * Returns keys ordered from Most Recently Used (MRU) to Least Recently Used (LRU)
   */
  public snapshotOrder(): Array<{ key: K; value: V }> {
    const result: Array<{ key: K; value: V }> = [];
    let curr = this.headSentinel.next;
    while (curr && curr !== this.tailSentinel) {
      result.push({ key: curr.key, value: curr.value });
      curr = curr.next;
    }
    return result;
  }

  private unlinkNode(node: DListNode<K, V>): void {
    const prevNode = node.prev!;
    const nextNode = node.next!;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
    node.prev = null;
    node.next = null;
  }

  private attachAfterHead(node: DListNode<K, V>): void {
    const firstRealNode = this.headSentinel.next!;
    node.next = firstRealNode;
    node.prev = this.headSentinel;
    this.headSentinel.next = node;
    firstRealNode.prev = node;
  }
}

/**
 * Singly Linked List Node & Floyd's Cycle Detection (Tortoise and Hare)
 */
class SListNode<T> {
  constructor(
    public value: T,
    public next: SListNode<T> | null = null
  ) {}
}

function detectCycleStart<T>(head: SListNode<T> | null): SListNode<T> | null {
  let slow = head;
  let fast = head;

  // Phase 1: Determine whether a cycle exists
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Phase 2: Mathematical invariant proves distance from head to cycle start
      // equals distance from meeting point to cycle start
      let entry = head;
      while (entry !== slow) {
        entry = entry!.next;
        slow = slow!.next;
      }
      return entry;
    }
  }
  return null;
}

// ============================================================================
// Verification & Execution
// ============================================================================
const cache = new LRUCache<string, string>(3);
cache.put("page:/home", "Home HTML");
cache.put("page:/articles", "Articles HTML");
cache.put("page:/tools", "Tools HTML");
console.log("Initial MRU -> LRU:", JSON.stringify(cache.snapshotOrder()));

// Access 'page:/home' so it jumps to MRU; 'page:/articles' becomes LRU
cache.get("page:/home");
console.log("After get('page:/home'):", JSON.stringify(cache.snapshotOrder()));

// Insert 4th item; 'page:/articles' (LRU) must be evicted automatically
cache.put("page:/about", "About HTML");
console.log("After put('page:/about'):", JSON.stringify(cache.snapshotOrder()));
console.log("Evicted 'page:/articles' lookup:", cache.get("page:/articles")); // undefined

// Verify Floyd's Cycle Detection on a 4-node cyclic list
const n1 = new SListNode("Node-1");
const n2 = new SListNode("Node-2");
const n3 = new SListNode("Node-3");
const n4 = new SListNode("Node-4");
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n2; // Cycle back to Node-2!

const cycleEntry = detectCycleStart(n1);
console.log("Cycle detected entering at:", cycleEntry?.value); // "Node-2"

---

4. Where Linked Lists Live in Modern Production Systems

1. The Linux Kernel: Intrusive Doubly Linked Lists (struct list_head)

In standard university textbooks, a linked list node wraps the data: Node<T> { data: T, next, prev }. This requires two heap allocations (one for the object, one for the node wrapper) and an extra pointer dereference.

The Linux kernel flips this inside out using Intrusive Linked Lists (include/linux/list.h). Instead of the list node containing the struct, the C struct embeds struct list_head { struct list_head *next, *prev; } directly inside itself! Using the container_of() macro (which subtracts the compile-time byte offset of the member), the kernel recovers the parent struct pointer with zero extra heap allocations and dramatically better cache locality. Process task descriptors (task_struct), page frame allocators, and network socket buffers all run on intrusive doubly linked lists.

2. React Fiber Architecture: Child / Sibling / Return Pointers

Early React (React 15 and below) reconciled the Virtual DOM recursively using the JavaScript call stack. If a component tree was huge, React couldn't pause rendering mid-way to handle a user's keystroke, causing dropped frames.

React 16+ introduced React Fiber, which transforms the component tree into a Singly Linked List of Fiber nodes connected by three pointers: child, sibling, and return (parent). Because traversal is driven by a pointer loop rather than recursive call frames, React can pause work after any Fiber node, yield to the browser's main thread to paint a frame, and resume right where its workInProgress pointer left off.

3. Memory Allocators (jemalloc, ptmalloc, Free Lists)

How does malloc() or a WebAssembly linear memory allocator know which freed chunks of memory are available for reuse? It cannot allocate a dynamic array to track free memory when it is the memory allocator! Instead, allocators write next and prev pointers directly inside the unused bytes of freed memory blocks, forming segregated Free Lists of available memory chunks.

---

5. The Professor's Architecture Cheat Sheet

When to Choose Linked Lists:

• LRU / LFU Eviction Queues & Connection Pools: Pairing a Hash Map with a Doubly Linked List gives unbeatable $O(1)$ touch-and-evict semantics.
• Kernel / Embedded / Lock-Free Queues: Intrusive linked lists allow zero-allocation movement of thread descriptors across wait queues and run queues.
• Pausable / Incremental Tree Walkers: Like React Fiber, linked pointers let you turn deep recursion into an interruptible state machine.

When NOT to Choose Linked Lists:

• Sequential scanning or searching: Never iterate a Linked List to search for a value ($O(n)$ with terrible cache locality).
• Memory-constrained mobile/IoT environments storing small primitives: Storing a 4-byte integer inside a Doubly Linked List node on a 64-bit OS requires two 8-byte pointers (prev and next) plus object header overhead—wasting over $80%$ of RAM on pointers alone! (You can inspect JSON payload sizes versus raw structures using our JSON Formatter and Data Size Converter).