Linked Lists Deep Dive
Implement singly, doubly, and circular linked lists; master pointer manipulation and cycle detection.
What you'll learn
- Singly, doubly, and circular linked list variants
- Pointer manipulation: insert, delete, reverse
- Floyd's cycle detection algorithm
- Merge sort on linked lists
Concept
Linked Lists Deep Dive
A linked list stores elements in nodes, each pointing to the next. Unlike arrays, linked lists do not store elements contiguously, so insertion and deletion at a known position is O(1) - you just relink pointers. The cost is O(n) random access.
Variants
Singly linked: each node has a next pointer. One-directional traversal. Doubly linked: each node has next and prev. Allows backward traversal and O(1) deletion given a node reference. Circular: the last node points back to the head. Useful for round-robin scheduling.
Pointer Manipulation
The key skill is drawing the pointers before and after. To insert node B after A: B.next = A.next; A.next = B. Order matters - if you set A.next = B first, you lose the reference to the old next. To reverse a list, maintain three pointers (prev, curr, next) and relink at each step.
Cycle Detection
Floyd's algorithm uses two pointers: a slow pointer (1 step) and a fast pointer (2 steps). If there is a cycle, they will meet. If the fast pointer reaches null, there is no cycle. This uses O(1) space.
Merge Sort on Lists
Merge sort is the natural sorting algorithm for linked lists: split at the midpoint (slow/fast pointer), recursively sort each half, then merge. It is O(n log n) with O(1) extra space.
Example
class Node { constructor(val) { this.val = val; this.next = null; } }
function fromArray(arr) {
const dummy = new Node(0); let tail = dummy;
for (const v of arr) { tail.next = new Node(v); tail = tail.next; }
return dummy.next;
}
function reverse(head) {
let prev = null, curr = head;
while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
return prev;
}
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;
}
function toArray(head) { const r = []; let c = head; while (c) { r.push(c.val); c = c.next; } return r; }
const list = fromArray([1, 2, 3, 4, 5]);
console.log('Original:', toArray(list));
console.log('Reversed:', toArray(reverse(list)));
reverse walks the list with three pointers, flipping each next to point backward. hasCycle uses Floyd tortoise-and-hare: if they meet, a cycle exists.
Try it
- JSON Formatter
Linked lists serialize to JSON arrays - see the structural difference between linked and contiguous storage.
Common mistakes
The mistake
Losing the rest of the list by breaking a pointer before saving it.
The fix
Always save the next pointer before overwriting. temp = curr.next; curr.next = newNext.
The mistake
Forgetting to handle edge cases: empty list, single node, two nodes.
The fix
Reverse of an empty list is empty. Reverse of a single node is itself. Test these explicitly.
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.