← Linked Lists · guided lesson
Linked Lists
the story
Singly linked list
Every tool here exists because something was too slow or broke without it. Here is what.
In 1956 Newell, Shaw and Simon were building the Logic Theory Machine, a program that searched for proofs in logic. Its data grew in shapes and sizes nobody could predict, so a fixed block of memory per list would either overflow or sit half empty. Their fix: each memory cell points to the next one, and new cells come from a shared pool of free cells — the first list-processing languages (IPL). A 1960 paper already named the price: the links ate about half the fast memory, and reaching the k-th item got slow.
the problem it solved
Storing data whose size and shape you can't know in advance, without reserving big fixed blocks that overflow or sit empty.
why it matters: without it
Every growing, splicing structure would need big up-front arrays and O(n) shifts — no cheap hash-table chains, free lists or O(1) cache eviction.
sources: Newell & Shaw — Programming the Logic Theory Machine (Western Joint Computer Conference, 1957) ↗ · Gelernter, Hansen & Gerberich — A FORTRAN-Compiled List-Processing Language (Journal of the ACM, 1960) ↗ · IEEE Computer Society — Herbert A. Simon, Computer Pioneer ↗
also in this chapter: Dummy head (sentinel node) · In-place reversal (prev / curr / next) · Fast & slow pointers (Floyd's cycle detection) · Doubly linked list + HashMap (the LRU cache)
the idea
The idea in 30 seconds
A linked list is a chain of nodes. Each node holds a value and a reference (next) to the node after it.
Nodes live anywhere in memory. Only the references hold the order — so inserting or deleting is just rewiring arrows, O(1) once you are at the spot.
The price: no indexes. To reach the 5th node you must walk 4 hops from head — O(n).
picture this
A web series where every episode page has only a Next episode link. Slipping a bonus episode in after episode 3 means changing one link. But to reach episode 7 from the start, you click Next six times — there is no "jump to 7".
watch it
Insert at a position
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Insert at a position
Walk `prev` to the node before the spot, then change exactly two references. The order of the two changes matters.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Delete by value with a dummy head
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Delete by value with a dummy head
Deleting = skipping. The removed node drops away because nothing points to it any more.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 9
Read it once. Say it out loud once. Bas.
A node is val + next. The list itself is just a reference to the first node, head. The last node's next is null.
key idea 2 of 9
Read it once. Say it out loud once. Bas.
Singly linked: one next. Doubly linked: prev + next, so you can remove a node you hold in O(1). Circular: the tail points back to the head.
key idea 3 of 9
Read it once. Say it out loud once. Bas.
Insert / delete is O(1) if you already hold the node before the spot. Finding that spot is O(n). Access by index is O(n) — the opposite trade-off from arrays.
key idea 4 of 9
Read it once. Say it out loud once. Bas.
Dummy head trick: put a fake node before head. Every real node now has a predecessor, so "change the head" stops being a special case. Return dummy.next.
key idea 5 of 9
Read it once. Say it out loud once. Bas.
Slow / fast pointers: fast moves 2, slow moves 1. Finds the middle, detects a cycle (Floyd), and finds the cycle's entry — all in O(1) space.
key idea 6 of 9
Read it once. Say it out loud once. Bas.
Order of rewiring matters: save curr.next before you overwrite it, or the rest of the list is lost forever.
key idea 7 of 9
Read it once. Say it out loud once. Bas.
Any "next" rule is a linked list: i → nums[i] turns an array into a chain, so Floyd can find a repeated value without extra memory (LC 287).
key idea 8 of 9
Read it once. Say it out loud once. Bas.
In Java, a node nobody references is garbage-collected — "deleting" means making it unreachable.
key idea 9 of 9
Read it once. Say it out loud once. Bas.
java.util.LinkedList is doubly linked. For interview problems you almost always write your own tiny ListNode; for a stack or queue, prefer ArrayDeque.
spot the pattern
When you see this, think this
"Middle of the list", "split in half", "palindrome list"
slow / fast pointers (fast moves 2)
"Cycle", "loop", "where does the loop start"
Floyd's tortoise and hare (then reset one pointer to head)
"n-th from the end" in one pass
Two pointers with a fixed gap of n
The head might change (delete head, merge, partition)
Dummy head node — return
dummy.next
+7 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Overwriting
curr.nextbefore saving it — the rest of the list becomes unreachable. - Dereferencing null:
fast.next.nextneedsfast != null && fast.next != nullchecked first, in that order.
quick check
One question. No pressure.
You hold a reference to a node in a singly linked list. Which operation is O(1)?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Reverse Linked List
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why put a dummy node in front of head?
Question 1: Why put a dummy node in front of head?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.