Learn · DSA · Pattern 5
Linked Lists
An array keeps its items shoulder-to-shoulder in memory. A linked list scatters them and connects each to the next with an arrow. That one change flips all the trade-offs.
Before we start
- What a linked list is and how it differs from an array
- Why insert/delete is cheap but “find the 5th” is not
- The moves: traverse, insert, delete, reverse
- The fast/slow pointer trick for middle & cycle detection
- Reverse a list and merge two sorted lists
- Detect a loop with two pointers
- Explain array vs linked list trade-offs out loud
Why you’re learning it: linked-list questions are interview bread-and-butter, and they force you to really understand pointers — the idea under trees, graphs, and a lot of real systems. ⏱️ ~30 min.
What is a linked list?
Think of a scavenger hunt. Each clue holds two things: a value (do this) and where the next clue is. You can’t jump to clue #5 — you must follow the chain from the start. Each “clue” is a node: a value plus a pointer to the next node. The last one points to null (the end).
Array vs Linked List — the trade-off
| Array | Linked List | |
|---|---|---|
| Get the 5th item | O(1) — jump by index | O(n) — follow the chain |
| Insert / delete in the middle | O(n) — shift everything | O(1) — just re-point arrows* |
| Memory | One solid block | Scattered nodes + pointers |
*Once you’re at the node. Arrays win for lookup; linked lists win for lots of inserts/deletes.
The moves
- Traverse: start at head, follow
nextuntilnull. - Insert: point the new node’s
nextat the following node, then point the previous node at the new one. - Delete: point the previous node’s
nextpast the one you’re removing. - Reverse: walk the list flipping each arrow to point backwards — the #1 interview question.
The fast/slow pointer trick
Two pointers again: one moves 1 step, the other 2. When the fast one reaches the end, the slow one is at the middle. And if the list has a loop, the fast pointer eventually laps and meets the slow one — that’s how you detect a cycle.
Where you’ll use it — real life
Each state points to the previous one — a linked list is the natural fit.
“Next song”, browser back/forward — nodes linked forward (and back).
A doubly-linked list + hashmap is the classic “least-recently-used” cache — a real system-design answer.
Stacks, queues, hash-table buckets and graphs all lean on linked nodes.
Why we practice this
Pointers are slippery on paper — reps are where “re-point next” stops being scary. Reverse-a-list especially: master it and half of linked-list problems fall.
Now YOU do the reps
Out loud: “How does a linked list differ from an array, and when would I choose each?” Then log it in your Journal.
Back to your Siemens roadmap →