Linked List

⏱️ ~4-minute bite · solve the sandbox to master

0%lesson

🧒

5-Year-Old Metaphor

— The physical, real-world picture. No jargon.

🚂 A train where each car knows only the car directly behind it — to reverse the train, uncouple and recouple one car at a time.

What a linked list is

An array stores everything in a contiguous block of memory — each element lives at a fixed offset. A linked list is different: each node can live anywhere in memory. The only connection is that each node holds a pointer (a memory address) to the next node.

Node { value: 1, next: → Node {value: 2, next: → Node {value: 3, next: null} } }

Each node: two fields. That's it.

Linked list wins

Insert/delete at head: O(1) — just rewire one pointer
Insert in middle (with pointer): O(1)
No pre-allocated size — grows on demand
Efficient as a queue, stack, or deque backbone

Linked list loses

Random access: O(n) — must walk from head
No binary search (no index)
Extra memory per node (the pointer itself)
Poor cache locality — nodes scattered in memory

The reversal intuition (the #1 interview operation)

Each car of our train knows only the car in front of it (its next pointer). To reverse the train, you walk car by car and flip each car's coupler to point backward instead of forward. You need a "spare coupler" (the prev variable) to remember where to point it, and you must save the next car's address before you cut the forward coupler.

Three variables. One pass. O(n) time, O(1) space. No extra list needed.

Singly vs Doubly linked list

Singly: prev ← [val | next→] → next (one pointer per node)

Doubly: ← [prev | val | next] → (two pointers — can walk both ways)

A doubly linked list makes delete-in-place O(1) without needing a separate "find the predecessor" pass. LRU Cache (the eviction algorithm) is a doubly linked list + hashmap.

🎛️

Interactive Sandbox

— Move something, see it react instantly.

How to use: Step through the reversal one frame at a time. Watch arrows flip as curr advances and prev trails behind. The ✕ means the forward link has been severed.

null

curr

→

null

● prev● curr● next← reversed arrow✕ severed link

null

node 1

curr

1 / 6

step

[INIT]Initial: prev=null, curr=head (node 1). About to save curr.next as 'next'.

🎯

Challenge

Step through to complete the linked list reversal [1→2→3→4→5] → [5→4→3→2→1].

Try it

🎯

Why Should I Care?

— The exact interview question + the bug it kills.

Exact interview question — reverse a linked list

"Reverse a singly linked list in-place. O(n) time, O(1) space."

1	interface ListNode {
2	val: number;
3	next: ListNode \| null;
4	}
5
6	function reverseList(head: ListNode \| null): ListNode \| null {
7	let prev: ListNode \| null = null;
8	let curr = head;
9	while (curr !== null) {
10	const next = curr.next; // 1. save next
11	curr.next = prev; // 2. flip arrow
12	prev = curr; // 3. advance prev
13	curr = next; // 4. advance curr
14	}
15	return prev; // new head
16	}
17	// Time: O(n) Space: O(1)

Classic follow-up — detect a cycle (Floyd's algorithm)

"Given a linked list, return true if it contains a cycle."

1	function hasCycle(head: ListNode \| null): boolean {
2	let slow = head;
3	let fast = head;
4	while (fast !== null && fast.next !== null) {
5	slow = slow!.next; // 1 step
6	fast = fast.next.next; // 2 steps
7	if (slow === fast) return true; // caught!
8	}
9	return false;
10	}
11	// If there's a cycle: fast laps slow, they meet.
12	// If no cycle: fast hits null first.
13	// Time: O(n) Space: O(1)

Senior follow-up — merge two sorted lists

1	function mergeTwoLists(
2	l1: ListNode \| null,
3	l2: ListNode \| null,
4	): ListNode \| null {
5	const dummy = { val: 0, next: null } as ListNode;
6	let cur = dummy;
7	while (l1 && l2) {
8	if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
9	else { cur.next = l2; l2 = l2.next; }
10	cur = cur.next!;
11	}
12	cur.next = l1 ?? l2; // attach the remaining tail
13	return dummy.next;
14	}
15	// Dummy head trick: avoids special-casing an empty result.
16	// Time: O(n+m) Space: O(1)

Complexity comparison: linked list vs array

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at head	O(n) shift	O(1)
Insert at tail	O(1) amort.	O(n) or O(1)*
Insert in middle	O(n) shift	O(1) w/ pointer
Delete at head	O(n) shift	O(1)

* O(1) insert at tail requires keeping a tail pointer. Common in queue implementations.

🔬

The Deep Dive

— Spec refs, engine internals, the minutiae.

The dummy-head pattern — simplifies every linked list problem

Most linked list bugs involve special-casing the head node. A dummy head (a sentinel node before the real list) eliminates these cases: you can always do cur.next = someNode without checking "is this the first node?".

1	// Without dummy — must handle head separately
2	function removeNthFromEnd(head: ListNode, n: number): ListNode \| null {
3	// ... complicated head-removal check
4
5	// With dummy — uniform handling
6	function removeNthFromEnd(head: ListNode, n: number): ListNode \| null {
7	const dummy = { val: 0, next: head } as ListNode;
8	let fast: ListNode \| null = dummy;
9	let slow: ListNode \| null = dummy;
10	for (let i = 0; i <= n; i++) fast = fast!.next; // n+1 ahead
11	while (fast !== null) { fast = fast.next; slow = slow!.next; }
12	slow!.next = slow!.next!.next; // remove target
13	return dummy.next;
14	}

Recursive reversal — why you should know it but not use it

1	function reverseListRec(head: ListNode \| null): ListNode \| null {
2	if (!head \|\| !head.next) return head; // base: 0 or 1 node
3	const newHead = reverseListRec(head.next); // recurse to end
4	head.next.next = head; // flip: next node points back at head
5	head.next = null; // sever head's forward pointer
6	return newHead;
7	}
8	// Time: O(n) Space: O(n) ← call stack depth!

Recursive reversal is elegant but uses O(n) stack space. For a list of 100,000 nodes you'd blow the call stack. Interviewers often ask: "can you do this iteratively?" — the iterative version (O(1) space) is almost always preferred.

Fast & slow pointer — the general pattern

Floyd's cycle detection is one instance of a broader pattern: two pointers moving at different speeds to find a structural property without extra memory.

Find middle: when fast reaches the end, slow is at the middle. Useful for "reverse second half" problems.
Find cycle entry: after detection, reset one pointer to head and advance both at speed 1 — they meet at the cycle entrance.
Find Nth from end: advance fast N steps, then move both until fast hits null.

When does a linked list appear in production code?

LRU Cache — doubly linked list + hashmap. The list maintains access order; the map gives O(1) lookup. Every get/put is O(1).
Browser history — doubly linked list. Back/forward navigation is O(1) pointer hops.
Undo/redo stacks — singly linked list where each node stores a delta or snapshot.
React Fiber — the reconciler internally uses a linked work-unit tree (each fiber is a node with child, sibling, return pointers).

Common implementation bugs

Forgetting to save next before flipping: the most common reversal bug. After curr.next = prev, the original next is gone unless you saved it first.
Off-by-one on "Nth from end": count carefully whether N is 1-indexed or 0-indexed. Test with a 1-node list and N=1.
Not handling null / single-node input: every linked list function should handle head === null as its first check.

🎤

Interview Questions

— Real questions from real interviews — with answers.

prev, curr, next — you need 'next' to save the forward link before flipping curr.next.

If a cycle exists, fast gains 1 step per round on slow — they must eventually collide.

A sentinel node before the list's head eliminates head-insertion/deletion special cases.

Fast/slow pointers: when fast reaches the end, slow is at the middle.

Hashmap (O(1) lookup) + doubly linked list (O(1) reorder) — the two structures together give O(1) get and put.

🎮

Memory Game

— Quick quiz — lock the concept in long-term memory.

1/4

In Floyd's algorithm, if the list has no cycle, what happens to the fast pointer?