A treasure hunt at a college fest. The first clue is in your hand, and every clue tells you where the next one is hidden. Want clue 7? You must follow clues 1 to 6 first — there is no shortcut.
Annoying, right? But now watch the flip side. The organiser wants to slip a brand-new clue between clue 3 and clue 4. In the cinema-hall world of arrays, everyone from seat 4 onward would have to shift. Here? She rewrites exactly one chit — clue 3 now points to the new clue, the new clue points to old clue 4. Done. Nothing else moved.
That's a linked list: terrible at jumping to position k, brilliant at splicing things in and out. The exact mirror image of the array you just studied — and that mirror is the point of learning both.
The structure: nodes and next-pointers
Each element lives in a node: a small box holding two things — a value, and the address of the next node. The nodes themselves sit anywhere in memory; nothing is adjacent. One special pointer, the head, remembers where the chain begins, and the last node's next is None — the end of the treasure hunt.
class Node:
def __init__(self, val):
self.val = val
self.next = None # address of the next node (the chit)
# build 12 -> 99 -> 37 by hand:
head = Node(12)
head.next = Node(99)
head.next.next = Node(37)Walking the list (and why access is O(n))
Student question: where is list[500]?
Nobody knows — not even the list. Node 500's address is written on node 499's chit, which is written on node 498's chit... There is no address arithmetic, because nothing is adjacent. The only way to reach position k is to walk k links:
current = head
while current: # stops when current becomes None
print(current.val)
current = current.next # follow the chitResult
12 99 37
So: access by position is O(n). If your workload is "give me the i-th element" all day, a linked list is the wrong tool, full stop. What did we buy by paying that price? Splicing.
Insert and delete: rewiring chits
Suppose you are already holding a node, and you want to insert a new value right after it. Watch how little happens:
def insert_after(node, val): # O(1)
new = Node(val)
new.next = node.next # 1. new node grabs the onward address
node.next = new # 2. old node points to the new one
def delete_after(node): # O(1)
if node.next:
node.next = node.next.next # skip over the victim
def push_front(head, val): # O(1) - rewire the head
node = Node(val)
node.next = head
return node # the new headTwo pointer writes. Not one element shifted, whether the list has 10 nodes or 10 crore. But look closely at the order of those two lines in insert_after — the new node grabs the onward address before the old node is rewired. Swap them and node.next is overwritten first — the rest of the list becomes unreachable, silently. Hold that thought; it becomes the central drama of the reversal section.
One honest asterisk: the O(1) applies when you already hold the node. Finding the right spot still costs an O(n) walk. Interviewers probe this distinction deliberately — "O(1) insertion" without the asterisk is a half-truth.
Array vs linked list, honestly
Quick self-test before the table: which structure for a music queue where songs are constantly reordered? And which for a leaderboard you read by rank?
| Operation | Array | Linked list |
|---|---|---|
| Access element k | O(1) — address maths | O(n) — walk k links |
| Insert/delete at the front | O(n) — everything shifts | O(1) — rewire the head |
| Insert/delete after a HELD node | O(n) | O(1) — two pointer writes |
| Search by value | O(n) | O(n) |
| Memory per element | just the data | data + pointer(s) |
| CPU cache friendliness | excellent — contiguous | poor — scattered |
Arrays win at reaching; linked lists win at rearranging. (Music queue → list; leaderboard by rank → array. If you got both, the lesson is landing.)
Two patterns that solve most list questions
Pattern 1 — fast & slow pointers. Problem: find the middle of a list in ONE pass. The natural approach — count the nodes (one pass), walk to n/2 (second pass) — works, but the interviewer asks for one pass. Think about it: what if two people walked the list together, one moving twice as fast?
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
return slow # fast at the end => slow at the middleWhen fast has covered the whole list, slow — moving at half speed — has covered exactly half. One pass. (slow doesn't mean "bad pointer"; it simply moves one step at a time.)
And the same two runners answer a spookier question: does the list contain a cycle — a chit pointing back to an earlier clue, trapping walkers forever? On a straight list, fast reaches None. In a cycle, both runners loop forever — but fast gains one position on slow every step, so on a circular track it must catch him:
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # same NODE (is), not same value
return True
return False # fast fell off: no cycleThis is Floyd's cycle detection — O(n) time, O(1) space. (Storing visited nodes in a set also works but costs O(n) memory; "can you do it without extra space?" is the interviewer asking for Floyd by name.)
Pattern 2 — the dummy head. A fake node placed before the real head, so "insert at the front" and "the list might become empty" stop being special cases — every operation becomes the same middle-of-list operation. You'll use it in the merge exercise and thank it quietly forever after.
The big one: reversing a list
The most-asked linked list question in existence: reverse 1 → 2 → 3 → 4 in place, so it becomes 4 → 3 → 2 → 1.
What would we naturally do? Copy the values into a Python list, reverse that, write them back. Correct — and it uses O(n) extra memory while dodging the skill being tested. The real question is: can you do it by flipping the arrows themselves, with no extra memory?
Let's discover the algorithm instead of memorising it. Walk the list left to right, and at each node, make its arrow point backwards. To flip an arrow I need to know two things: the node in front of me, and the node behind me. So I'll carry two pointers — current (where I stand) and prev (where I came from).
Pause — there's a trap coming. The moment I flip current's arrow to point backwards... how do I move forward? The forward address was stored in that arrow, and I just overwrote it. The rest of the list is gone.
That's the entire difficulty of the problem, and the fix is one discipline: save the onward address BEFORE flipping the arrow.
def reverse(head):
prev = None # nothing behind me yet
current = head
while current:
nxt = current.next # 1. SAVE the rest of the list
current.next = prev # 2. flip the arrow backwards
prev = current # 3. I become the "behind" node
current = nxt # 4. step forward using the saved address
return prev # current is None; prev is the old tail = new headDry run: watch the arrows flip
Follow it on paper too — every iteration, all four steps:
start: prev=None current=1 list: 1 -> 2 -> 3 -> 4
iter 1: nxt=2 1.next=None prev=1 current=2
state: None <- 1 2 -> 3 -> 4
iter 2: nxt=3 2.next=1 prev=2 current=3
state: None <- 1 <- 2 3 -> 4
iter 3: nxt=4 3.next=2 prev=3 current=4
iter 4: nxt=None 4.next=3 prev=4 current=None -> stop
return prev = 4: 4 -> 3 -> 2 -> 1 -> NoneNote the last line: we return prev, not current — current has walked off the end and is None. Returning the wrong one is the final classic slip.
Why does the reversal work?
Say this invariant out loud — it is the proof, and interviewers love hearing it: "at the start of every iteration, everything behind prev is already reversed, and everything from current onward is untouched." Each iteration moves exactly one node from the untouched side to the reversed side, so after n iterations the whole list is reversed. One pass, O(n) time, O(1) space — and no step of it needs to be memorised, because steps 1–4 are forced: save (or lose the list), flip (the actual work), advance both pointers (progress).
What if...?
What if the list is empty? The while loop never runs; we return prev = None. An empty list reversed is an empty list. Correct for free.
What if there's one node? One iteration: its arrow flips to None (it was already None), prev becomes that node. Correct.
What if two nodes point to the same node? Then it isn't a simple list any more — that's how cycles and Y-shaped merges happen, and it's why cycle detection compares nodes with is (identity), never == (values) — two different nodes can hold the same value.
What if I'm asked to do it recursively? Same idea, with the call stack carrying what prev carried — which means O(n) stack space instead of O(1). Offer the iterative version first and say why.
Doubly linked lists (and the LRU story)
One more upgrade. Give every node a second pointer — prev — and the list becomes walkable in both directions. Why pay double the pointer bookkeeping? Here is the problem that justifies it.
An LRU cache (least-recently-used — how your phone decides which app to evict from memory) must, on every access, yank an arbitrary node out of the middle of a recency list in O(1). Unlinking a node means updating its predecessor's next-pointer. In a singly linked list, how do you find the predecessor? Walk from the head — O(n). In a doubly linked list, it's just node.prev:
def unlink(node): # O(1), no walking
node.prev.next = node.next
if node.next:
node.next.prev = node.prevOne extra pointer per node buys O(1) removal of any held node — exactly what LRU needs. The complete LRU design (hash map + doubly linked list working together) is built in lesson 12.
Common mistakes
- Overwriting
.nextbefore saving it — the silent lost-list bug. Before any pointer write, ask: does anything still need the old value? - Returning
current(None) instead ofprevfrom reversal. - Comparing values instead of nodes in cycle detection —
slow is fast, neverslow.val == fast.val. - Writing
while fast.nextwithoutfast and— crashes on even-length lists when fast becomes None. - Not testing the empty list and single node — walk your code through both before calling it done.
- Claiming O(1) insertion "anywhere" — it's O(1) at a node you already hold; finding the spot is O(n).
How do I recognise linked list problems?
- "in one pass" on a list → fast & slow pointers (middle, cycle, k-th from end with two pointers k apart).
- "without extra space" on a list → pointer surgery (reversal, reorder), not value copying.
- "the head might change" (insert at front, delete the head) → dummy head.
- O(1) removal from the middle of an ordering (LRU, browser history) → doubly linked list, usually paired with a hash map.
And a meta-clue: if the problem hands you a linked list, the intended solution almost always lives in pointer manipulation. An answer that converts to an array first is usually the fallback, not the target.
Quick revision
| Operation | Singly LL | Doubly LL | Note |
|---|---|---|---|
| Access k-th | O(n) | O(n) | no address arithmetic exists |
| Insert/delete at head | O(1) | O(1) | rewire, don't shift |
| Delete a held node | O(n) — needs predecessor | O(1) — has .prev | the LRU reason |
| Reverse | O(n), O(1) space | O(n) | save → flip → advance |
| Middle / cycle | O(n), fast & slow pointers | O(1) space | |
One thing to remember
In a linked list, the structure IS the pointers — so before you overwrite any pointer, save what it held. Every linked list bug ever written is someone forgetting that sentence.
Practice Zone — PYQs from real selection rounds
Six MCQs, then the big three: reversal with a full dry run, merging two sorted lists with a dummy head, and deleting the k-th node from the end in one pass.
The defining difference between an array and a linked list is:
Asked in
Accessing the 500th element of a singly linked list costs:
Asked in
To find the middle of a singly linked list in one pass, the standard technique is:
Asked in
Floyd's cycle detection declares a cycle when:
Asked in
While reversing a singly linked list iteratively, the loop body must (in order):
Asked in
Why does an LRU cache use a doubly linked list rather than a singly linked one?
Asked in
Hands-on tasks:
Reverse the list 1 → 2 → 3 → 4 → None iteratively, in O(1) extra space. Then dry-run the pointers for the first two iterations.
Asked in
Merge 1 → 3 → 5 and 2 → 4 → 6 into one sorted list by relinking nodes (no new nodes for data). Why does a dummy head make this cleaner?
Asked in
Remove the 2nd node from the end of 1 → 2 → 3 → 4 → 5 in ONE pass. (Two pointers, k apart.)
Asked in
FAQ
Where are linked lists actually used in real systems?
Inside LRU caches (with a hash map), OS schedulers and free-memory lists, music queues, undo systems, and as collision chains inside hash tables. You rarely build one directly in Python — but they live inside structures you use daily.
Why does Python have no built-in linked list?
Because collections.deque covers the common need (O(1) at both ends), and dynamic arrays beat lists at everything index-related thanks to CPU caches. Interviews still ask linked lists because they test pointer reasoning — the skill, not the container.
How do I find where a cycle BEGINS, not just that it exists?
After fast and slow meet, reset one pointer to the head and walk both one step at a time — they meet again exactly at the cycle's entry. It falls out of the distance algebra of Floyd's algorithm, and it's the standard follow-up once you've detected the cycle.
Singly or doubly linked — which should I use by default?
Singly, until an operation demands backwards reach — O(1) removal of a held node, or reverse iteration. The second pointer doubles the rewiring work on every insert and delete, so pay for it only when something needs it (LRU does; a simple stack of nodes doesn't).
Pointer discipline unlocked. Next, two structures so simple they are just rules — and they quietly run half your computer — Lesson 4: Stacks & Queues →