Linked Lists

If arrays are slabs of contiguous memory, linked lists are the opposite: nodes scattered across the heap, held together by pointers. They trade away O(1) random access in exchange for O(1) insertion and deletion *anywhere you already have a pointer*. That trade-off — and the pointer juggling it requires — is what every linked-list problem is really testing.

What a Linked List Actually Is

A linked list is a chain of nodes, where each node carries some data plus a reference (pointer) to the next node. The list is found by following pointers from a single \head\ reference; the chain ends at \null\.

\\\` head → [10

→] → [25

→] → [30

→] → [45

/] \\\`

Each node typically looks like:

\\\`js class Node { constructor(data) { this.data = data; this.next = null; } } \\\`

Three points worth burning into your head:

1. Nodes are not contiguous — they live wherever the allocator put them. 2. There is no \arr[i]\ for free. To reach the i-th node you walk \i\ pointers — that's O(n) access. 3. The whole list dies if you lose the head. There's no "size" stored at the front unless you maintain it.

Singly vs Doubly vs Circular

Singly	Doubly	Circular
Pointers per node	1 (\next\)	2 (\next\, \prev\)	1 or 2; last → first
Walk forward	yes	yes	yes
Walk backward	no	yes	depends
Insert at head	O(1)	O(1)	O(1)
Insert at tail	O(n) (or O(1) with tail ptr)	O(1)	O(1)
Delete given a node	O(n) (need prev)	O(1)	O(n) or O(1)
Memory per node	data + 1 ptr	data + 2 ptrs	data + 1–2 ptrs
Typical use	stacks, queues, simple chains	LRU caches, browser history	round-robin, Josephus problem

A doubly linked list is what production data structures usually want — the extra pointer pays for O(1) deletion and bidirectional traversal.

A circular list has the last node point back to head. Useful when you want "infinite" traversal (round-robin scheduling, music playlist on repeat).

Daily Operations You'll Reuse

\\\`js // Insert at head — O(1) function pushFront(head, x) { const node = new Node(x); node.next = head; return node; // new head }

// Insert after a known node — O(1) function insertAfter(prev, x) { const node = new Node(x); node.next = prev.next; prev.next = node; }

// Delete a node given the node BEFORE it — O(1) function removeAfter(prev) { if (prev.next) prev.next = prev.next.next; }

// Search by value — O(n) function find(head, x) { for (let p = head; p !== null; p = p.next) { if (p.data === x) return p; } return null; } \\\`

Notice every "constant-time" operation needs a pointer to the right place. The whole skill of linked-list code is never losing pointers.

Beginner Mistakes to Skip

1. Losing the rest of the list when reversing. Always save \current.next\ into a temp before overwriting it. 2. Off-by-one when you need the node *before* the i-th. To delete the i-th node, you stop at index \i − 1\, not \i\. 3. Forgetting the empty-list case. \head === null\ blows up most one-liner solutions. Always check. 4. Forgetting the single-node case. Many algorithms assume \head.next\ exists. 5. Mutating \head\ without returning it. When you delete the head, the *caller's* head reference is now stale unless you return the new one. 6. Comparing nodes by value when you mean by reference. \p === q\ is identity; \p.data === q.data\ is value.

Intermediate: The Dummy / Sentinel Node

A fake "before-the-head" node that exists only to simplify code:

\\\`js const dummy = new Node(null); dummy.next = head; // ... do work, treat dummy.next as the real head ... return dummy.next; \\\`

Why use it? Because then head insertion and deletion stop being special cases. Every real node has a "previous" node, even the original head. Use it for:

• merging two sorted lists
• removing the n-th node from the end
• partitioning a list around a value
• removing all nodes with a given value

The amount of \if (head === null)\ boilerplate it eliminates is enormous.

Intermediate: The Two-Pointer Toolkit

Three problems, one technique: slow advances 1 step, fast advances 2.

\\\`js // Find the middle node — O(n), O(1) space function middle(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow; } \\\`

\\\`js // Detect a cycle (Floyd's Tortoise & Hare) — O(n), O(1) space function hasCycle(head) { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) return true; } return false; } \\\`

To find the k-th node from the end in one pass: send one pointer k steps ahead, then walk both at speed 1 until the leader hits null.

The reason Floyd's works: if there's a cycle, the fast pointer enters it and gains 1 step per iteration on the slow pointer. They must collide within one cycle length. To then find the cycle *start*, reset one pointer to head and walk both at speed 1 — they meet at the entry. (The math is a clean modular-arithmetic argument; trust it for now and revisit later.)

Intermediate: Reversing a Linked List

The interview classic. Iterative is the one you should be able to write in your sleep:

\\\`js function reverse(head) { let prev = null, curr = head; while (curr) { const next = curr.next; // save before overwriting curr.next = prev; // flip the link prev = curr; // advance prev curr = next; // advance curr } return prev; // new head } \\\`

Three pointers, one node reversed per loop iteration. O(n) time, O(1) space.

The recursive version is shorter but uses O(n) stack space:

\\\`js function reverse(head) { if (!head || !head.next) return head; const newHead = reverse(head.next); head.next.next = head; head.next = null; return newHead; } \\\`

The trick: trust the recursion to reverse everything after \head\, then fix the one link that's still wrong.

Intermediate: Merging Two Sorted Lists

\\\`js function merge(a, b) { const dummy = new Node(null); let tail = dummy; while (a && b) { if (a.data <= b.data) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = a || b; return dummy.next; } \\\`

O(n + m) time, O(1) space. Note how the dummy node makes this elegant — without it you'd need an awkward "first iteration" branch.

Advanced: Cache & Memory Cost

For n integers (4 bytes each):

Structure	Total bytes	Per-element overhead
Array	4n	0
Singly linked	≥ 12n (data + 8-byte pointer + allocator overhead)	3×
Doubly linked	≥ 20n	5×	Worse than the size: cache misses. Iterating an array is mostly L1 hits; iterating a linked list is often a cache miss per node. In modern hardware that's a 10–100× slowdown for "the same Big-O". Linked lists are *almost never* the right choice for "store many small values and iterate them". Advanced: Where Linked Lists Genuinely Win	Use case	Why
LRU Cache	doubly linked list + hash map → O(1) move-to-front
OS scheduler / free lists	O(1) splicing of nodes
Adjacency lists for graphs	grow without resizing
Persistent / functional lists	append-front shares structure
Linked-list intrusive structures in C	no allocation, embed \next\ in the object itself

Outside these, prefer arrays / deques / hash maps. Most JavaScript code that "needs a linked list" actually needs an array.

Advanced: Classic Problems That Look Hard, Aren't

• Detect & locate cycle start — Floyd's then walk from head.
• Palindrome check — find middle, reverse second half, compare halves.
• Intersection of two lists — pointers swap to the other head when they hit null; they meet at the intersection (or at null) after at most n+m steps.
• Copy list with random pointer — clone each node *next-to* its original, fix random pointers from neighbours, then split.
• Reverse in groups of k — reverse one group, recursively reverse the rest, splice.

The trick with all of them is drawing the pointers before you write code. If you can't draw it, you can't write it.

Advanced: A Word on Java / Python / C++ Standard Lists

• Java \LinkedList\ is doubly linked. Most code that uses it would be faster with \ArrayDeque\.
• C++ \std::list\ is doubly linked; \std::forward_list\ is singly linked.
• Python doesn't have a built-in linked list — \collections.deque\ covers most needs.
• JavaScript has no built-in. Roll your own \Node\ class for interview problems.

Practice Path

1. Build a singly linked list manually with three nodes \1 → 2 → 3\. Print all values, then reverse and print again. 2. Implement \hasCycle(head)\ (Floyd's). Test on a list with no cycle and a list whose tail points back to node 2. 3. Solve Merge Two Sorted Lists (LC 21) iteratively with a dummy node. 4. Solve Remove Nth Node From End of List (LC 19) in one pass using two pointers and a dummy.