Chapter 08 — Linked Lists
Chapter 08 — Linked Lists
Hey everyone! Welcome back to Namaste DSA!
An array stores everything side by side in memory. A linked list takes the opposite approach: each element (a node) sits anywhere in memory and holds a pointer to the next one. This trade-off makes some operations O(1) that arrays do in O(n) — and vice versa.
What we will cover:
- Node = value + pointer to next
- Singly vs Doubly vs Circular
- Why insert/delete is O(1) but access is O(n)
- Reversing a linked list (the #1 interview question)
- Finding the middle (slow/fast)
- Detecting a cycle (Floyd's algorithm)
- Merging two sorted lists
- Interview Questions
1. What is a Node?
┌─────────────────────────────────────────────────────────────┐ │ SINGLY LINKED LIST │ ├─────────────────────────────────────────────────────────────┤ │ │ │ head │ │ │ │ │ ▼ │ │ ┌────┬───┐ ┌────┬───┐ ┌────┬───┐ │ │ │ 10 │ ●─┼──►│ 20 │ ●─┼──►│ 30 │ ✗ │ → null │ │ └────┴───┘ └────┴───┘ └────┴───┘ │ │ value next value next value next │ │ │ └─────────────────────────────────────────────────────────────┘
class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
2. Singly vs Doubly vs Circular
| Type | Each node points to | Note |
|---|---|---|
| Singly | next only | Lightest; one-way traversal |
| Doubly | next AND prev | Walk both ways; more memory |
| Circular | last node → back to head | No null end; useful for round-robin |
3. Why Access is O(n) but Insert/Delete is O(1)
ARRAY vs LINKED LIST
─────────────────────────────────────────────
Array Linked List
Access [i] O(1) O(n) ← must walk from head
Insert front O(n) O(1) ← just repoint head
Delete front O(n) O(1)
Search O(n) O(n)
There's no address formula for a linked list — nodes are scattered in memory, so to reach the i-th node you must hop through the pointers one by one (O(n)). But inserting/deleting at a known position is just rewiring a couple of pointers — no shifting like arrays — so it's O(1).
INSERT 15 after node 10 — just repoint: before: [10] ──► [20] step 1: new node [15] ──► [20] (point new to next) step 2: [10] ──► [15] (point prev to new) result: [10] ──► [15] ──► [20] ✔ no shifting!
4. Reversing a Linked List (THE Interview Question)
Walk the list flipping each next pointer backwards. Track three things: prev, curr, and the saved next.
function reverse(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next; // 1. save next
curr.next = prev; // 2. flip pointer
prev = curr; // 3. advance prev
curr = next; // 4. advance curr
}
return prev; // new head
}
HAND TRACE: 1 → 2 → 3 → null prev=null curr=1 save next=2; 1.next=null; prev=1; curr=2 list: 1→null save next=3; 2.next=1; prev=2; curr=3 list: 2→1→null save next=null;3.next=2; prev=3; curr=null list: 3→2→1→null return prev=3 → 3 → 2 → 1 → null ✔
5. Finding the Middle (Slow/Fast)
Slow moves 1 step, fast moves 2. When fast reaches the end, slow is at the middle.
function middle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next; // +1
fast = fast.next.next; // +2
}
return slow; // middle node
}
6. Detecting a Cycle (Floyd's Tortoise & Hare)
If the list loops, the fast pointer will eventually lap and meet the slow one. If fast reaches null, there's no cycle.
function hasCycle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true; // they met → cycle!
}
return false; // fast hit the end
}
// O(n) time, O(1) space — no extra Set needed!
7. Merging Two Sorted Lists
function mergeTwo(a, b) {
const dummy = new ListNode(0); // dummy head simplifies edge cases
let tail = dummy;
while (a && b) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a || b; // attach whatever remains
return dummy.next;
}
Pro tip: a dummy head node removes annoying "is the list empty?" edge cases — you always have a node to attach to.
Interview Questions — Quick Fire!
Q: Why is accessing the i-th element of a linked list O(n)?
"Unlike arrays, linked-list nodes aren't contiguous in memory, so there's no address formula. To reach the i-th node you must follow next pointers one at a time from the head, which is O(n)."
Q: When is a linked list better than an array?
"When you do many insertions or deletions at the front or middle and don't need random access. Those are O(1) for a linked list (just rewiring pointers) versus O(n) for an array (shifting elements). Arrays win when you need fast index access or cache-friendly iteration."
Q: How do you reverse a linked list?
"Iterate with three pointers: prev, curr, and a saved next. For each node, save its next, point its next back to prev, then advance prev and curr forward. When curr is null, prev is the new head. It's O(n) time, O(1) space."
Q: How does Floyd's cycle detection work?
"Use two pointers, slow moving one step and fast moving two. If there's a cycle, fast eventually laps and meets slow. If fast reaches the end (null), there's no cycle. It uses O(1) space, unlike the hash-set approach which uses O(n)."
Q: What is a dummy node and why use it?
"A placeholder node placed before the real head. It removes special-casing for an empty list or for inserting at the front, because you always have a node to attach to. You return dummy.next at the end. It's common in merge and removal problems."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| Node | value + next pointer. |
| Access | O(n) — no address formula. |
| Insert/delete | O(1) at a known node — just rewire. |
| Reverse | prev/curr/next, flip each pointer. |
| Middle & cycle | slow/fast pointers, O(1) space. |
| Dummy node | Removes head/empty edge cases. |
What's Next?
Chapter 09: Stacks — the LIFO structure behind undo buttons, balanced-parentheses checks, and the call stack itself.
Keep coding, keep grinding! See you in the next one!
Post a Comment