Chapter 8 — Linked Lists

An array is contiguous. A linked list is scattered.
That difference in memory layout is the difference in what's cheap and what's expensive.

Part 1: Why Linked Lists Exist

Chapter 2 showed arrays are contiguous blocks of memory. That layout gives O(1) random access (base + i × size) but makes insertions and deletions at arbitrary positions O(n) — you must shift everything after the insertion point.

What if insertions and deletions at arbitrary positions must be fast? You give up contiguity. Each element lives wherever the allocator placed it in memory. To find the next element, you follow a pointer stored in the current element.

This is a linked list.

The fundamental tradeoff:

The linked list is not universally better or worse. It's a different set of tradeoffs. Choose arrays when you need fast access by index. Choose linked lists when you need fast arbitrary insert/delete and traverse-only access.

Part 2: Physical Reality — What a Node Is

A node is a small object in memory containing two things:

1. The value (the actual data).
2. A pointer (memory address of the next node).

In JavaScript:

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;  // null = no next node (end of list)
  }
}

A linked list is just a reference to the head node. Nothing more. The rest of the list is reachable by following next pointers.

Memory layout:

[node A: val=1, next=→] → [node B: val=2, next=→] → [node C: val=3, next=null]
   at address 0x100           at address 0x240            at address 0x3F8

head = 0x100 (pointer to A)

Addresses are arbitrary. Node A is at 0x100, Node B at 0x240, Node C at 0x3F8 — they are not adjacent in memory. To go from A to B, you must read A's next field (which stores 0x240) and jump to that address. This jump is a pointer dereference — and it's a potential cache miss, unlike array indexing which accesses memory sequentially (cache-friendly).

Part 3: Singly vs Doubly Linked List

Singly linked list: Each node has only a next pointer. Traversal is forward-only. You cannot go backward.

head → [1|→] → [2|→] → [3|null]

Doubly linked list: Each node has both next and prev pointers. Traversal is bidirectional.

null ← [←|1|→] ↔ [←|2|→] ↔ [←|3|→] → null

Doubly linked lists enable O(1) deletion of a node if you have a direct reference to it — you can fix up both neighbors without needing to find the previous node first. This is why LRU Cache uses a doubly linked list.

class DoublyNode {
  constructor(val) {
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

Space cost: Each doubly-linked node stores two pointers instead of one. In a 64-bit system, that's 8 extra bytes per node (one extra pointer). For millions of nodes, this matters.

Part 4: Building a Linked List — Key Operations

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Insert at head: O(1)
  prepend(val) {
    const node = new Node(val);
    node.next = this.head;
    this.head = node;
    if (this.tail === null) this.tail = node;
    this.length++;
  }

  // Insert at tail: O(1) with tail pointer
  append(val) {
    const node = new Node(val);
    if (this.tail === null) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
  }

  // Delete by value (first occurrence): O(n)
  delete(val) {
    if (!this.head) return;

    // Special case: head is the target
    if (this.head.val === val) {
      this.head = this.head.next;
      if (!this.head) this.tail = null;
      this.length--;
      return;
    }

    // Find the node before the target
    let curr = this.head;
    while (curr.next && curr.next.val !== val) {
      curr = curr.next;
    }

    if (curr.next) {
      if (curr.next === this.tail) this.tail = curr;
      curr.next = curr.next.next;
      this.length--;
    }
  }

  // Access by index: O(n)
  get(index) {
    let curr = this.head;
    for (let i = 0; i < index; i++) {
      if (!curr) return null;
      curr = curr.next;
    }
    return curr ? curr.val : null;
  }
}

Why delete at head is special: To delete any node, you need the node before it (to update its next pointer). For the head, there's no node before it — you just update this.head directly.

Part 5: The Dummy Node (Sentinel) Technique

Many linked list problems have awkward edge cases when the operation touches the head. The standard fix: add a dummy node before the head.

const dummy = new Node(0);
dummy.next = head;

Now "the node before the head" always exists — it's dummy. This eliminates the head-special-case in most operations.

Example: delete all nodes with value val

Without dummy:

// Must handle head separately, messy
while (head && head.val === val) head = head.next;
let curr = head;
while (curr && curr.next) {
  if (curr.next.val === val) curr.next = curr.next.next;
  else curr = curr.next;
}
return head;

With dummy:

const dummy = new Node(0);
dummy.next = head;
let curr = dummy;
while (curr.next) {
  if (curr.next.val === val) curr.next = curr.next.next;
  else curr = curr.next;
}
return dummy.next;

Same logic, no special case. dummy.next at the end is the new head. Use a dummy node anytime you might need to delete the head or insert before the head.

Part 6: Reversing a Linked List — Iterative

Problem: Given a linked list 1 → 2 → 3 → 4 → 5, reverse it to 5 → 4 → 3 → 2 → 1.

This is the most fundamental linked list operation. Understand it cold.

The trick: iterate through the list, at each step reversing one next pointer.

You need three pointers: prev (the new "next" for current node), curr (node being processed), next (saved reference to next node before we overwrite curr.next).

function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    const next = curr.next;   // 1. save next (we're about to break this link)
    curr.next = prev;         // 2. reverse the pointer
    prev = curr;              // 3. move prev forward
    curr = next;              // 4. move curr forward
  }

  return prev;  // prev is the new head (last node of original list)
}

Full Dry Run: reverseList(1→2→3→4→5)

Initial: prev=null, curr=1→2→3→4→5

Step 1:
  next = curr.next = 2→3→4→5
  curr.next = prev = null        (1→null)
  prev = curr = node(1)
  curr = next = node(2)
  State: null ← 1   2→3→4→5

Step 2:
  next = curr.next = 3→4→5
  curr.next = prev = node(1)     (2→1→null)
  prev = node(2)
  curr = node(3)
  State: null ← 1 ← 2   3→4→5

Step 3:
  next = node(4)
  curr.next = node(2)            (3→2→1→null)
  prev = node(3)
  curr = node(4)
  State: null ← 1 ← 2 ← 3   4→5

Step 4:
  next = node(5)
  curr.next = node(3)            (4→3→2→1→null)
  prev = node(4)
  curr = node(5)

Step 5:
  next = null
  curr.next = node(4)            (5→4→3→2→1→null)
  prev = node(5)
  curr = null

curr === null → loop ends. return prev = node(5).

Result: 5→4→3→2→1→null ✓

Why prev starts as null: The original head becomes the new tail. The new tail's next must be null. Starting prev = null ensures the original head's next gets set to null correctly in step 1.

Complexity: O(n) time, O(1) space.

Part 7: Reversing — Recursive Version

function reverseListRecursive(head) {
  // Base case: empty list or single node
  if (!head || !head.next) return head;

  // Recursive leap of faith: reverseListRecursive(head.next)
  // returns the new head of the reversed suffix
  const newHead = reverseListRecursive(head.next);

  // head.next is now the TAIL of the reversed suffix
  // Make it point back to head
  head.next.next = head;
  head.next = null;

  return newHead;
}

Dry run (abbreviated): reverseListRecursive(1→2→3)

reverseListRecursive(1):
  reverseListRecursive(2):
    reverseListRecursive(3): return node(3).  ← base case, single node
    head=2, head.next=3. 3.next = 2. 2.next = null.
    Return node(3).
  head=1, head.next=2. 2.next = 1. 1.next = null.
  Return node(3).

Result: 3→2→1→null ✓

The key line: head.next.next = head — after recursion returns, head.next is still the second node, but that node is now the tail of the reversed sublist. We make it point back to head, completing the reversal.

Complexity: O(n) time, O(n) space (n stack frames). Prefer iterative for production — no stack overflow risk.

Part 8: Finding the Middle — Fast/Slow Pointers

Problem: Find the middle node of a linked list in one pass.

Use fast/slow pointers (from Chapter 5). slow moves one step at a time, fast moves two. When fast reaches the end, slow is at the middle.

function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

Dry run: list = 1→2→3→4→5

slow=1, fast=1.
  slow=2, fast=3.
  slow=3, fast=5.
  fast.next=null → loop ends.
return slow = node(3). ✓ (middle of 5-element list)

Dry run: list = 1→2→3→4 (even length)

slow=1, fast=1.
  slow=2, fast=3.
  slow=3, fast=null (fast.next.next — fast is at 3, fast.next is 4, fast.next.next is null).
  fast is not null (fast=4 after first iteration), wait...

Let me retrace:

slow=1, fast=1.
Iter 1: slow=2, fast=3.    (fast=1.next.next=3)
Iter 2: slow=3, fast=null? (fast=3.next.next=4.next=null. But while condition is fast&&fast.next)
  fast=3, fast.next=4. Both truthy → enter loop. slow=3, fast=4.next.next=null.
  Wait: fast=3. fast.next=4. slow=slow.next=3. fast=fast.next.next=3.next.next=4.next=null.
Iter 3: fast=null. Loop condition: fast && fast.next → false. Stop.
return slow = node(3). (first of two middles for even-length list)

For a 4-element list, this returns the second-of-two-middle-nodes... actually node 3 (1-indexed), which is the first of the two middle elements. Different interview problems want different midpoints — always check whether "upper middle" or "lower middle" is needed.

Part 9: The Doubly Linked List — LRU Cache Preview

The doubly linked list's power is O(1) deletion of any node when you have a direct reference to it.

class DoublyLinkedList {
  constructor() {
    // Sentinel head and tail — no null checks needed
    this.head = new DoublyNode(-1);  // dummy head
    this.tail = new DoublyNode(-1);  // dummy tail
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  // Insert node right after head (most recently used position)
  insertFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  // Remove a node (O(1) because we have direct reference)
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // Remove and return the node just before tail (least recently used)
  removeLast() {
    if (this.tail.prev === this.head) return null;  // empty
    const last = this.tail.prev;
    this.remove(last);
    return last;
  }
}

Why two sentinel nodes? They eliminate all boundary checks. insertFront always has a valid this.head.next. removeLast always has a valid this.tail.prev. Without sentinels, every operation needs to handle "is the list empty?" and "is this the first/last node?" This is the same dummy-node technique from Part 5, applied to both ends.

The LRU Cache design:

LRU (Least Recently Used) cache evicts the least recently accessed item when capacity is exceeded. The data structure needed: O(1) get, O(1) put, O(1) eviction of the least recently used.

The solution: doubly linked list + HashMap.

• HashMap: key → node (for O(1) lookup).
• Doubly linked list: nodes ordered by recency (most recently used at head, least recently used at tail).
• On get(key): find node via HashMap, move it to the front (O(1) doubly linked delete + O(1) insert at front).
• On put(key, val): if key exists, update and move to front. If capacity exceeded, remove tail node (O(1)) and delete its key from HashMap.

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();  // key → node
    this.list = new DoublyLinkedList();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this.list.remove(node);
    this.list.insertFront(node);  // mark as most recently used
    return node.val;
  }

  put(key, val) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = val;
      this.list.remove(node);
      this.list.insertFront(node);
    } else {
      const node = new DoublyNode(val);
      node.key = key;  // store key in node for eviction
      this.map.set(key, node);
      this.list.insertFront(node);

      if (this.map.size > this.capacity) {
        const evicted = this.list.removeLast();
        this.map.delete(evicted.key);
      }
    }
  }
}

Dry run: LRUCache(2) with operations: put(1,1), put(2,2), get(1), put(3,3), get(2)

put(1,1): map={1→node1}. list: [head↔node1(key=1,val=1)↔tail].
put(2,2): map={1→n1,2→n2}. list: [head↔n2↔n1↔tail].
  (n2 inserted at front = most recent)
get(1): n1 found. Remove from middle, insert at front.
  list: [head↔n1↔n2↔tail]. return 1.
put(3,3): capacity=2, size would be 3.
  Insert n3 at front. list: [head↔n3↔n1↔n2↔tail].
  Evict last (n2, key=2). map.delete(2).
  map={1→n1, 3→n3}. list: [head↔n3↔n1↔tail].
get(2): map.has(2) → false. return -1. ✓
  (2 was evicted because it was LRU when 3 was inserted)

LRU Cache is LeetCode 146 (Hard) and is asked at virtually every tech company. The insight — HashMap for O(1) lookup + doubly linked list for O(1) ordered eviction — is a fundamental systems design pattern.

Part 10: Merging Two Sorted Linked Lists

Problem: Merge two sorted linked lists into one sorted linked list.
mergeTwoLists(1→2→4, 1→3→4) → 1→1→2→3→4→4

This is the merge step of merge sort applied to linked lists. Two pointers, one on each list. Compare frontmost values, advance the pointer on the smaller side.

function mergeTwoLists(l1, l2) {
  const dummy = new Node(0);
  let curr = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      curr.next = l1;
      l1 = l1.next;
    } else {
      curr.next = l2;
      l2 = l2.next;
    }
    curr = curr.next;
  }

  // Attach remaining list (one of them is already exhausted)
  curr.next = l1 || l2;

  return dummy.next;
}

Dry run: mergeTwoLists(1→2→4, 1→3→4)

dummy→curr. l1=1→2→4, l2=1→3→4.

l1.val=1, l2.val=1. 1<=1 → curr.next=l1(1). l1=2→4. curr=node(1).
l1.val=2, l2.val=1. 2>1 → curr.next=l2(1). l2=3→4. curr=node(1) [from l2].
l1.val=2, l2.val=3. 2<=3 → curr.next=l1(2). l1=4. curr=node(2).
l1.val=4, l2.val=3. 4>3 → curr.next=l2(3). l2=4. curr=node(3).
l1.val=4, l2.val=4. 4<=4 → curr.next=l1(4). l1=null. curr=node(4) [from l1].

l1=null → loop ends. curr.next = l2 = node(4→null).

Result: dummy→1→1→2→3→4→4→null. return dummy.next. ✓

Complexity: O(n + m) time, O(1) space. The dummy node eliminates the special case of "what is the initial head of the merged list?"

Part 11: Mental Model

Reach for a linked list when:

1. Frequent insertion or deletion at the beginning or middle. O(1) once you have the position vs O(n) for arrays.
2. Unknown or highly variable size. No pre-allocation needed. Each node is allocated individually.
3. Implementing stacks, queues, or deques. Doubly linked list is the natural implementation of a deque with O(1) both ends.
4. The problem hands you node references directly. If you already have a pointer to a node, you can delete/insert in O(1) — you don't need to find it.

Do not use a linked list when:

1. You need random access by index. O(n) per access makes it unusable as an array replacement.
2. Cache performance matters. Scattered memory → cache misses → real-world slowness even when asymptotic complexity is the same.
3. Memory is tight. Each node carries pointer overhead (8 bytes per pointer on 64-bit systems).

Interview-specific patterns:

• Dummy node: Use it anytime the head could be modified or deleted.
• Fast/slow pointers: Find middle, detect cycle, find cycle entry, find nth from end.
• Reverse in place: Know both iterative (3 pointers) and recursive (backtrack) versions cold.
• Multiple passes are fine: First pass finds length/middle, second pass does the work. Still O(n).

Part 12: Real Systems

Redis Linked List (LOLWUT):
Redis's List type is internally a doubly linked list (for large lists) or a ziplist (compact encoding for small lists — Chapter 2's "ziplist threshold" noted this). LPUSH / RPUSH are O(1). LRANGE is O(S+N) where S is the offset and N the range size. Task queues built on Redis use BRPOPLPUSH — atomically pop from one list and push to another, which is how reliable queue semantics are implemented (the item exists in transit until acknowledged).

Browser History (Doubly Linked List):
Each page visit is a node. back moves current = current.prev. forward moves current = current.next. Navigating to a new page: current.next = newNode, truncating the forward history. This is exactly a doubly linked list with a cursor.

Node.js Streams:
Node.js readable streams internally buffer chunks of data in a linked list. When the consumer is slow (backpressure), new chunks are pushed to the tail. When the consumer reads, chunks are pulled from the head. The linked list allows dynamic-size buffering without pre-allocation. The _readableState.buffer is a BufferList (linked list of Buffer objects).

PostgreSQL Buffer Pool:
PostgreSQL's shared buffer pool (the page cache for database files) uses a clock-sweep algorithm for eviction, implemented over a doubly linked list of buffer descriptors. Pages recently accessed move to the "hot" end. The clock hand sweeps from the "cold" end, evicting pages with low usage counts. LRU-like behavior in production.

OS Memory Allocator (Free List):
The kernel's memory allocator maintains a free list — a linked list of available memory blocks. malloc removes a block from the free list. free inserts a block back. Doubly linked allows O(1) coalescing of adjacent free blocks. glibc's ptmalloc and jemalloc use variants of this. Every dynamic memory allocation in your Node.js process traces back to a linked list operation in the allocator.

V8 Garbage Collector:
V8's incremental GC marks live objects and reclaims dead ones. Dead objects are added to a "free list" of available slots in memory, also a linked list. When you create a new object, V8 first checks the free list for a suitable slot rather than always asking the OS for new memory.

Part 13: Vocabulary Map

Part 14: 5 Practice Problems

1. Trace and Predict

function f(head) {
  if (!head || !head.next) return head;
  let prev = null, curr = head;
  while (curr) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

You know what this does. Now trace it on 1→2→3→null AND on null (empty list). What happens at each step with the empty list? Is the empty list handled correctly by the code? Now: does this function work correctly for a circular linked list? Why or why not?

2. Find the Waste

To check if a linked list is a palindrome, a naive approach copies all values to an array, then checks the array with two pointers. O(n) time, O(n) space.

Design an O(n) time O(1) space approach using only linked list operations. Outline the three steps. (Hint: find middle, reverse second half, compare, optionally restore. Why is the "optionally restore" step important in production?)

3. Failure Analysis

function deleteNode(node) {
  // Given only the node to delete (not head), delete it from the list.
  node.val = node.next.val;
  node.next = node.next.next;
}

This is LeetCode 237. The approach copies the next node's value into the current node, then deletes the next node. When does this approach FAIL? (Give a specific case where it cannot work.) What invariant does the problem guarantee to make this approach valid?

4. Design Under Constraints

Design sortList(head) — sort a linked list in O(n log n) time and O(1) space (ignoring recursion stack).

Hint: merge sort on a linked list. The merge step is O(n) and O(1) space (unlike arrays, no copying — just pointer manipulation). The split step uses findMiddle. What is the recursion depth? What is the space complexity if you count the recursion stack? How would you implement merge sort iteratively (bottom-up) to achieve true O(1) space?

5. Reach Beyond

Design reverseKGroup(head, k) (LeetCode 25 — Hard): reverse every k nodes in a linked list. Nodes remaining at the end (fewer than k) stay as-is.

reverseKGroup(1→2→3→4→5, k=2) → 2→1→4→3→5
reverseKGroup(1→2→3→4→5, k=3) → 3→2→1→4→5

Steps: check if k nodes remain (don't reverse otherwise), reverse k nodes, recursively handle the rest, connect. What is the time and space complexity?

Connect Forward

Chapter 9 — Binary Search applies to sorted arrays and has no direct linked list connection. But Chapter 10 — Trees is built on the same pointer-based node structure. A tree node is a linked list node with two next pointers (left and right) instead of one. Everything you learned here — dummy nodes, pointer manipulation, recursive structure — applies directly to trees.

Chapter 8a dives into the most important linked list interview problems: Reorder List (split + reverse + merge), Palindrome Linked List (find middle + reverse half + compare), Copy List With Random Pointer, and the full LRU Cache implementation.

Connect Backward

Chapter 7 (Stack & Queue) used an array to implement a stack and a two-pointer index to implement a queue. Those were array-backed implementations. The "proper" queue implementation (O(1) enqueue and dequeue) can be a linked list — enqueue appends to tail O(1), dequeue removes from head O(1). No index tricks needed, no shifting.

Chapter 5 (Two Pointers) introduced fast/slow pointers on linked lists — cycle detection (Floyd's algorithm, fully worked in Chapter 5a) and nth-from-end removal. Those are linked list problems solved with the two-pointer lens.