Module P-2·18 min read

Node-based structures, singly vs doubly linked lists, and the reversal/cycle-detection operations every list problem builds on.

JJS

Written by Jatin Jain Saraf · Senior Software Engineer

Module P-2 — Linked Lists: Singly, Doubly, and Core Operations

Q: Why is `insertAfter` genuinely O(1), while finding the node to insert after (if you don't already have a reference to it) is O(n)?

`insertAfter` only reassigns a small, fixed number of pointers (`newNode.next` and `node.next`) regardless of the list's length or the new node's position — no other node is touched or shifted. Locating an arbitrary node without an existing reference, however, requires traversing from the head one node at a time, since there's no arithmetic shortcut (unlike array indexing) to jump directly to it. — Given a reference to `node`, inserting after it touches exactly two pointers — the new node's `next` and `node`'s `next` — regardless of where `node` sits in the list or how long the list is; that's genuinely O(1) work. The cost only appears if you don't already have that reference and need to find it first, which (unlike an array's direct index arithmetic from Module F-2) requires walking from the head, node by node, until you reach it — O(n) in the worst case. Option A is false — the O(1) cost holds for insertion after any node you already hold a reference to, not just the first one. Option C contradicts the module's explicit and correctly justified distinction between the two operations. Option D fabricates a nonexistent JavaScript engine behavior; linked lists implemented with plain objects/classes are not silently converted to arrays.

Q: Why can a doubly linked list delete an arbitrary node in O(1) given just a reference to that node, while a singly linked list cannot do the same without additional work?

Deleting a node requires updating its neighbors' pointers to skip over it — a doubly linked list's `prev` pointer gives direct access to the preceding node without any search, while a singly linked list has no way to reach a node's predecessor except by traversing from the head, making that lookup O(n). — To delete a node, its predecessor's `next` pointer must be updated to skip over it. In a doubly linked list, `node.prev` gives immediate, O(1) access to that predecessor. In a singly linked list, there is no backward pointer at all — finding the predecessor requires starting at the head and walking forward until the node just before the target is reached, which is O(n) in the worst case. This is exactly the trade-off the module highlights as the reason the extra `prev` pointer earns its keep. Option A fabricates a nonexistent separate-array mechanism; neither structure stores values in an auxiliary array by default. Option C is false — singly linked lists absolutely support deletion; the module explicitly discusses it, just noting its O(n) predecessor-finding cost rather than claiming it's impossible. Option D directly contradicts the module, which explicitly and specifically contrasts O(1) (doubly) against O(n) (singly) for this exact operation.

Q: In `hasCycle`, why is it guaranteed that `slow` and `fast` will eventually point to the exact same node if the list contains a cycle, rather than the two pointers simply passing each other forever without ever meeting?

`fast` gains exactly one extra step on `slow` every iteration; once both pointers are inside the cycle, this steadily shrinking gap between them (measured going around the loop) must eventually reach exactly zero, since it decreases by one each iteration and a gap of zero means they occupy the same node — the same reasoning as a faster runner lapping a slower one on a circular track. — Because `fast` advances two nodes per iteration and `slow` advances one, once both are traveling around the same cycle, the distance between them (measured along the cycle) decreases by exactly one node per iteration. A strictly decreasing non-negative integer gap must eventually hit zero — at which point both pointers are on the same node. This is the same "lapping" intuition the module gives explicitly: a faster runner on a loop is guaranteed to eventually catch up to and meet a slower one, precisely because the gap between them can only shrink, never grow or skip over zero. Option B invents a fabricated iteration-limit mechanism that does not appear anywhere in the code. Option C is false — both pointers start at the same node (`head`), not different ones. Option D is incorrect and contradicts the module — Floyd's algorithm is a mathematically guaranteed correct cycle-detection method, not a heuristic with accepted false negatives.

What this module covers: Every structure so far in this course has been array-backed — one contiguous block of memory (Module F-2). A linked list breaks that assumption: each element is its own independently allocated node, connected by pointers rather than physical adjacency. This module covers singly and doubly linked lists, why insertion/deletion trade places with arrays on cost, reversal, and the cycle-detection technique previewed in Module F-8, now applied directly.

A Node-Based Structure

Where an array is one block with elements at predictable offsets, a linked list is a chain of individually allocated nodes, each holding a value and a pointer to the next node:

typescript

class ListNode<T> {
  value: T;
  next: ListNode<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

// 1 -> 2 -> 3 -> null
const third = new ListNode(3);
const second = new ListNode(2);
second.next = third;
const head = new ListNode(1);
head.next = second;

There is no address = base + i × size arithmetic here (Module F-2) — to reach the third node, you have to follow head.next.next, visiting each node in between. That's the fundamental trade: array indexing is O(1); linked list indexing (or "get the k-th element") is O(n).

Analogy: An array is the apartment building from Module F-2 — walk straight to unit 47. A linked list is a treasure hunt where each clue only reveals the location of the next clue — you cannot skip to clue 47 without having followed clues 1 through 46 first.

Where Linked Lists Win

The trade runs the other way for insertion and deletion at a known position. Inserting into the middle of an array means shifting every subsequent element (Module F-2); inserting into a linked list is just pointer reassignment — no other node moves at all:

typescript

function insertAfter<T>(node: ListNode<T>, value: T): void {
  const newNode = new ListNode(value);
  newNode.next = node.next;
  node.next = newNode;
  // O(1) — no other node in the entire list was touched or moved
}

This is genuinely O(1), regardless of how long the list is — a real, meaningful advantage over an array's O(n) middle-insertion cost, provided you already have a reference to the node you're inserting after. Finding that node in the first place is still O(n) if you don't already have a pointer to it, which is the honest caveat behind "linked lists have O(1) insertion" — it's O(1) insertion at a known point, not O(1) insertion at an arbitrary position you still have to search for.

Singly vs Doubly Linked Lists

A singly linked list (above) only points forward — from a given node, you can reach the next one, but not the previous one. A doubly linked list adds a prev pointer too:

typescript

class DoublyListNode<T> {
  value: T;
  next: DoublyListNode<T> | null = null;
  prev: DoublyListNode<T> | null = null;
  constructor(value: T) {
    this.value = value;
  }
}

The extra pointer costs a small amount of memory per node, but it buys something a singly linked list can't do cheaply: deleting a node in O(1), given only a reference to that node — no need to separately track or search for its predecessor, because the node already knows who it is:

typescript

function deleteNode<T>(node: DoublyListNode<T>): void {
  if (node.prev) node.prev.next = node.next;
  if (node.next) node.next.prev = node.prev;
  // O(1) — both neighbors are reachable directly from `node`, no search needed
}

In a singly linked list, deleting a given node requires first finding its predecessor by traversing from the head — O(n) — specifically because there's no prev pointer to jump backward through. This exact capability — O(1) deletion of an arbitrary known node — is the reason Module P-3's LRU Cache is built on a doubly linked list, not a singly linked one.

Reversing a Linked List

Reversal is the linked-list equivalent of Module F-2's array reversal, but the mechanism is entirely different — instead of swapping values in place, you re-point every next pointer to face the other direction:

typescript

function reverseList<T>(head: ListNode<T> | null): ListNode<T> | null {
  let prev: ListNode<T> | null = null;
  let curr = head;

  while (curr !== null) {
    const nextTemp = curr.next; // save the next node before we overwrite curr.next
    curr.next = prev;           // reverse this node's pointer
    prev = curr;                // advance prev
    curr = nextTemp;            // advance curr to the node we saved
  }

  return prev; // prev is now the new head
}

Each node's next pointer is flipped exactly once, so this is O(n) time, O(1) extra space — no new nodes allocated, just pointers redirected in place, one pass. This same "three-pointer shuffle" (prev, curr, nextTemp) is the standard shape for a large fraction of linked list problems: whenever you need to modify pointers as you walk the list, you generally need a reference to where you came from, where you are, and where you're going next — because once you overwrite curr.next, the original "next" is gone unless you saved it first.

Cycle Detection, Concretely

Module F-8 previewed Floyd's fast/slow pointer technique in the abstract. Here it is applied directly to a linked list:

typescript

function hasCycle<T>(head: ListNode<T> | null): boolean {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next; // moves twice as fast as slow

    if (slow === fast) return true; // they've met — there's a cycle
  }

  return false; // fast reached the end — no cycle
}

If the list has no cycle, fast reaches null and the loop ends cleanly. If there is a cycle, fast and slow are both trapped inside it, and because fast gains one extra step on slow every iteration, it's guaranteed to eventually land on the exact same node as slow — they can't pass each other without colliding, the same way a faster runner on a looping track eventually laps a slower one. This runs in O(n) time and, notably, O(1) space — no Set of visited nodes required (which would also solve the problem, in O(n) space, using the hash-based "have I seen this?" pattern from Module F-4 instead).

Merging Two Sorted Lists

A pattern that reappears directly in Module P-9 (Merge Sort): given two already-sorted linked lists, merge them into one sorted list by repeatedly taking whichever head is smaller.

typescript

function mergeSorted(a: ListNode<number> | null, b: ListNode<number> | null): ListNode<number> | null {
  const dummy = new ListNode(0); // placeholder — makes edge cases at the head disappear
  let tail = dummy;

  while (a !== null && b !== null) {
    if (a.value <= b.value) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }

  tail.next = a !== null ? a : b; // attach whatever's left of the non-exhausted list
  return dummy.next;
}

This is O(n + m) — every node from both lists is visited exactly once — and O(1) extra space, since it reassigns existing nodes' pointers rather than creating new ones. The dummy node is a small, common trick worth naming: it sidesteps a special case for "what's the head when the merged list is empty so far," letting the loop body treat every iteration identically.

Where This Shows Up in Your Stack

The DOM is a tree of nodes connected by pointers, not an array — parentNode, childNodes, nextSibling, previousSibling are exactly the next/prev relationships from this module, just branching into a tree instead of a single chain (Module P-4 covers tree structure in full).
Blockchain transaction chains: each block holds a reference to the previous block's hash — a singly linked list where "next" points backward in time instead of forward, and where reversing the direction of traversal (walking from genesis block forward) requires exactly this module's insight about which pointer direction you actually have.
LRU cache eviction (Module P-3, immediately next): the O(1)-deletion-of-a-known-node property from the doubly linked list section above is the entire reason that structure is chosen over a singly linked list or a plain array for this specific job.
Why JavaScript code rarely hand-rolls linked lists for everyday use: modern CPUs are extremely fast at scanning contiguous memory (better cache locality) — an array's O(n) linear scan is often faster in practice than a linked list's O(n) pointer-chasing traversal, because each node in a linked list can live anywhere in memory, causing cache misses an array wouldn't. Linked lists earn their keep specifically when O(1) insertion/deletion at known points matters more than raw scan speed — which is a real but narrower set of cases than "generic list of things," where a plain array usually wins.

Summary

A linked list is a chain of independently allocated nodes connected by pointers, not one contiguous block — the opposite memory model from the array in Module F-2.
Indexing is O(n) (no arithmetic shortcut to the k-th node) but insertion/deletion at a known node is O(1) — no other node needs to shift, unlike an array.
Doubly linked lists add a prev pointer, enabling O(1) deletion of an arbitrary known node without first searching for its predecessor — the property Module P-3's LRU Cache depends on directly.
Reversal is a three-pointer shuffle (prev, curr, nextTemp) that flips every next pointer in one O(n) pass, O(1) extra space.
Cycle detection via fast/slow pointers (Module F-8, applied concretely here) finds a cycle in O(n) time and O(1) space, without needing a Set of visited nodes.
Arrays still usually win in practice for plain JavaScript code, because of cache locality — linked lists earn their place specifically when O(1) insert/delete at a known point is the dominant concern.

The next module, The LRU Cache: Hash Map + Doubly Linked List for O(1) Access, combines this module's doubly linked list directly with Module F-4's hash map to build the exact structure behind Redis-style cache eviction.

Knowledge Check

Why is insertAfter genuinely O(1), while finding the node to insert after (if you don't already have a reference to it) is O(n)?

Why can a doubly linked list delete an arbitrary node in O(1) given just a reference to that node, while a singly linked list cannot do the same without additional work?

In hasCycle, why is it guaranteed that slow and fast will eventually point to the exact same node if the list contains a cycle, rather than the two pointers simply passing each other forever without ever meeting?

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule P-1: Recursion and the Call Stack Next Module P-3: The LRU Cache: Hash Map + Doubly Linked List for O(1) Access

Discussion

Join the discussion

Loading comments...