Data structures · Pointers

Flip one arrow at a time

Q: What breaks if you flip the arrow before saving next?

You lose everything after curr . That next field was the only pointer to the rest of the list, so overwriting it makes the remaining nodes unreachable. On 1 → 2 → 3 → 4 the loop then reads the field it just overwrote, lands on nil, and returns after one turn with the single-node list 1 → nil .

Q: How much extra memory does the reversal use?

O(1) . Three pointer variables regardless of list length, and no new nodes are allocated — the same nodes are reused with different next fields. The recursive version is O(n) instead, because every call frame stays on the stack until the deepest one returns.

Why a linked list can add to the front for free but cannot jump to position 7 — and how three pointers turn 1 → 2 → 3 → 4 around without losing a single node.

Step the pointers yourself →

head → 1 → 2 → 3 → 4 → nil

→

head → 4 → 3 → 2 → 1 → nil

01 The idea

A chain of arrows, not a block of slots

An array keeps its elements in one continuous block of memory, so element 7 sits exactly seven slots after element 0. A linked list gives that up. Each element lives in its own small box called a node, and the node stores two things: the value, and the address of the node that comes after it. The boxes can sit anywhere in memory. The only thing holding them together is that chain of addresses.

That one change decides everything else. You cannot jump to position 7, because no arithmetic finds it — you start at the head and follow seven arrows, one memory read each. But you can add a node at the front without touching a single existing node, because adding to the front means writing exactly two pointers. The array pays the opposite bill: instant indexing, but every element shifts one slot right when something joins the front.

A node is a value plus an arrow to the next node. Every linked-list operation is just deciding which arrows to rewrite, and in what order.

NodeOne box in the chain. It holds a value and a pointer called next, which stores the address of the following node.

HeadThe pointer to the first node. Lose the head and you lose the whole list, because nothing else points to it.

nilThe end marker. The last node's next is nil, so a walk knows when to stop. Written null or None elsewhere.

02 Hand trace

Reversing 1 → 2 → 3 → 4 by hand

Take the list 1 → 2 → 3 → 4 → nil. Reversing it means the old tail becomes the head and every arrow turns around. The nodes themselves never move in memory — only the next field inside each one changes.

Walk it with three pointers. prev is the node behind you, curr is the node you are working on, and nxt is a scratch variable holding the node in front of you. Each row below shows what every node's next field contains after one turn of the loop, so a cell reads node→whatever its next points at. The rose cell is the arrow that just changed, and prev is always the node that curr worked on last turn.

start1→22→33→44→nil

turn 11→nil2→33→44→nilcurr = 1 · its arrow now ends the list

turn 21→nil2→13→44→nilcurr = 2 · now points back at 1

turn 31→nil2→13→24→nilcurr = 3 · now points back at 2

turn 41→nil2→13→24→3curr = 4 · now points back at 3

result1→nil2→13→24→3head = 4 · 4 → 3 → 2 → 1 → nil

Four nodes, four arrows, four turns of the loop, and the answer comes out of prev rather than curr — because the loop only stops once curr has walked one step past the end onto nil. Now look at turn 1 again. The moment node 1 stopped pointing at node 2, the only arrow reaching node 2 was gone. The trace survives that because nxt was written down first. Section 03 is that ordering, and nothing else.

03 The code

One line in the wrong place loses the list

Both versions below flip arrows with the same pointers and the same loop. The only difference is whether nxt is saved before or after the arrow is overwritten. The left one is what people write from memory under pressure; trace it on 1 → 2 → 3 → 4 and it hands back a one-node list.

Broken · flips before saving

reverse(head):  prev = nil  curr = head  while curr != nil:    curr.next = prev    # arrow flipped first    prev = curr    curr = curr.next    # this field is now prev  return prev

Correct · saves next first

reverse(head):  prev = nil  curr = head  while curr != nil:    nxt = curr.next     # save the rest first    curr.next = prev    # flip one arrow    prev = curr         # prev steps forward    curr = nxt          # curr steps forward  return prev           # prev is the new head

Why line 5 exists. nxt = curr.next is the only copy of node 2's address the program will have once the very next line runs. Nothing else in memory points at node 2. Writing it into a variable is not tidiness; it is the difference between a reversed list and three orphaned nodes.

Why the broken version stops after one turn. curr = curr.next reads a field that its own line 5 already overwrote, so it loads whatever prev was holding back at line 5 instead of the next node. On the first turn that value is nil, so curr becomes nil, the while condition fails immediately, and the function returns with one node in hand.

Why it returns prev and not curr. The loop exits when curr is nil, which is one step past the end. prev is standing on the last node it flipped — the old tail, which is exactly the new head.

05 Cheat sheet

Singly linked list against a dynamic array

Operation	Linked list	Array	Why
Read the k-th element	`O(n)`	`O(1)`	The array computes an address; the list follows k arrows, one memory read each.
Insert at the head	`O(1)`	`O(n)`	The list writes two pointers; the array shifts every element one slot right.
Insert after a node you already hold	`O(1)`	`O(n)`	One arrow in, one arrow out. No searching, no shifting.
Delete a node you only have a pointer to	`O(n)`	`O(n)`	A singly linked node cannot reach the node in front of it, so you walk to find the predecessor.
Append at the tail, no tail pointer	`O(n)`	`O(1) amortised`	The list walks the whole chain to find the end; the array appends in place and only occasionally doubles.
Reverse the whole list	`O(n)`	`O(n)`	Every arrow, or every element, is touched exactly once. The list does it with `O(1)` extra space.

No random accessReaching position k always costs k arrow follows, even when you already know k. There is no index arithmetic to exploit.

Cost per nodeEvery node carries one extra pointer — 8 bytes on a 64-bit machine — plus its own allocation. A list of small integers can spend more memory on arrows than on data.

Cache behaviourArray elements sit next to each other, so one fetch brings several. List nodes can be anywhere, so a walk often pays a cache miss per node. This is why arrays win in practice far more often than the table suggests.

06 Where & why

A linked list is not a faster array

It is slower at everything an array does by position, and the cheat sheet above shows it winning in only two of six rows — both of them inserts at a spot you are already standing on. It loses two rows outright and merely ties the remaining two. Its real value is narrow and specific: once you are already standing on a node, inserting or splicing there costs nothing extra, and the list never has to be copied to grow.

Reach for it when…

Other code holds pointers to individual nodesAn array reallocates as it grows and every stored index or pointer goes stale. A node keeps its address for life.

You are splicing whole runsMoving a block of nodes from one list into another is a handful of pointer writes, no matter how long the block is.

No single operation may stallThere is no doubling copy, so no individual insert ever costs O(n). That matters in real-time and kernel code.

The structure is intrusiveThe node lives inside the object being stored, so joining a list costs no allocation at all. This is how the Linux kernel tracks tasks.

Use something else when…

Situation	Better choice	Why
You read by index, or read far more than you write	Dynamic array — vector, ArrayList, Python list	`O(1)` indexing and contiguous memory, against `O(n)` and a likely cache miss per node.
You want fast pushes and pops at both ends	Deque or circular buffer — ArrayDeque, collections.deque	The same `O(1)` at both ends, in one block of memory, with no node allocation per push.
You need to find and delete an arbitrary value fast	Hash set or hash map	`O(1)` average lookup; the list still walks in `O(n)` just to locate the node.
You need the data kept in sorted order	Balanced BST, or a sorted array	`O(log n)` search. A sorted linked list still searches in `O(n)`, because binary search needs jumps and a chain has none.

In production you will reach for your language's dynamic array almost every time, and meet linked lists hiding inside other things — hash-map buckets, the doubly linked list in an LRU cache, an allocator's free list, the kernel's task list. Interviews still ask for pointer rewiring because it is the cleanest way to find out whether you can hold a data structure in your head.

07 Interview questions

What they actually ask

Answer in the order below and you will have covered most of a twenty-minute linked-list round. Say the numbers out loud; the complexity questions are where candidates hesitate.

What is a linked list?

A chain of nodes, where each node holds a value and a pointer to the next node. The nodes are not contiguous in memory, so the only way to reach node k is to start at the head and follow k pointers. In exchange you get O(1) insertion at the head, and O(1) insertion after any node you are already holding. Deletion is only O(1) if you hold the node before the one you want gone — a singly linked node cannot reach its own predecessor.

Why is indexing O(n) on a list when an array does it in O(1)?

Because a list has no address formula. An array element sits at base + k × size — one multiply and one add — so position is pure arithmetic. A list cannot do that, because the nodes can be anywhere in memory. The address of node k is only known by reading node k minus 1, so you pay one dependent memory read per node.

Why is inserting at the head O(1)?

You allocate one node, set its next to the current head, and move head to the new node. Two pointer writes, and no existing node is touched. An array has to shift every element one slot right to free position 0, which is O(n).

Walk me through reversing a singly linked list.

Keep three pointers: prev starting at nil, curr at the head, and a scratch nxt. Each turn: save nxt = curr.next, set curr.next = prev, then move prev = curr and curr = nxt. When curr is nil the loop stops and prev is the new head. O(n) time, O(1) extra space.

What breaks if you flip the arrow before saving next?

You lose everything after curr. That next field was the only pointer to the rest of the list, so overwriting it makes the remaining nodes unreachable. On 1 → 2 → 3 → 4 the loop then reads the field it just overwrote, lands on nil, and returns after one turn with the single-node list 1 → nil.

How much extra memory does the reversal use?

O(1). Three pointer variables regardless of list length, and no new nodes are allocated — the same nodes are reused with different next fields. The recursive version is O(n) instead, because every call frame stays on the stack until the deepest one returns.

Iterative or recursive reversal — which do you write?

Iterative. Same O(n) time, but O(1) space instead of O(n) stack frames, and a list of a million nodes will blow the stack in the recursive version. Mention that the recursive one reads more cleanly, then say why you did not pick it — interviewers are checking that you know the cost, not that you know the trick.

You are handed a pointer to a node in the middle. Can you delete it in O(1)?

Not properly, in a singly linked list. You cannot reach the node before it to redirect its arrow, so finding the predecessor is O(n). The standard trick is to copy the next node's value into this node and unlink the next node instead, which is O(1), but it fails on the tail and it silently breaks any pointer another part of the program holds to that next node.

How do you detect a cycle in a linked list?

Floyd's two pointers. slow moves one node per turn, fast moves two. If they ever land on the same node there is a cycle; if fast reaches nil there is not. O(n) time and O(1) space, against a visited-set approach which is also O(n) time but O(n) space.

Singly or doubly linked — how do you choose?

Hard

Given the head and an integer k, reverse every consecutive block of k nodes, leave a final block shorter than k untouched, and return the new head.

Follow-up

Each block is the loop you already know, but the block you just reversed has to be wired to the head of the next reversed block, which does not exist yet — so you carry the previous block's tail forward while you work.

Show the hint

Check first that k nodes remain; then reverse exactly k and remember two things — the node that started this block, which is now its tail, and the node curr is on, which starts the next block.