Worked examples — Linked list — singly - node structure, traversal, insert head - tail - middle, delete

This page is a drill. The parent note taught you the four moves — build a node, traverse, insert, delete. Here we throw every possible situation at those moves: empty lists, single-node lists, the front, the middle, the very end, values that aren't there, and one real-world word problem. If a scenario made you hesitate, you'll find it worked below.

Everything uses only what the parent already built: a Node with data and next, one external head pointer, and null (Python None) marking the end of the chain. If any word here feels new, it isn't — re-read the parent's Section 1.

The scenario matrix

Every linked-list operation lives in one of these cells. A cell is defined by what the list looks like and where the action lands. The examples below hit every cell at least once.

Example 1 — Cell C: insert at head of a non-empty list

Forecast: guess the final list and which of the two wiring steps must come first. Write it down before reading.

1. Create the node. new = Node(5), so new.data = 5 and new.next = None. Why this step? A node must exist and hold its value before we can wire it into the chain.
2. Wire the new node forward: new.next = head. Now new points at the old first node 10. Why this step? This is the "look before the door moves" rule. The only handle on the chain 10 -> 20 -> 30 is head. We copy it into new.next while we still have it.
3. Move the front door: head = new. Why this step? new is now the first node, so the external head pointer must open onto it.

Final list: 5 -> 10 -> 20 -> 30 -> null.

Verify: length went from 3 to 4 (we added one). Walking from the new head: 5, 10, 20, 30 — old order preserved, new value at front. Insert-at-head touches a fixed two pointers regardless of list size ⇒ $O(1)$, matching the parent's table.

Example 2 — Cell B: insert at head of a single-node list

Forecast: does insert-head need a special case when the list has exactly one node? Guess yes/no.

1. Create: new = Node(7). Why? Same as always — node before wiring.
2. Wire forward: new.next = head ⇒ new.next points at the node 42. Why? The old front node is 42; new must look at it.
3. Move door: head = new.

Final: 7 -> 42 -> null.

Verify: length 1 → 2. Traversal yields 7, 42. No null was dereferenced. ✓

Example 3 — Cell A: every operation on an empty list

Forecast: which of these must not crash, and which must do nothing?

1. (a) traverse: cur = head = None. The loop is while cur is not None, which is while None is not None → False immediately. Prints nothing, no crash. Why safe? The parent chose while cur is not None precisely so an empty list is a valid zero-iteration case.
2. (b) insert_head(9): new = Node(9); new.next = head = None; head = new. Now 9 -> null. Why it works with no special case? Wiring new.next = None is exactly what a lone node needs.
3. (c) insert_tail(9): the code checks if self.head is None: → true → self.head = new; return. Result 9 -> null. Why the guard exists? Without it, cur = head = None then cur.next would raise AttributeError. This is the parent's explicit empty-list special case.
4. (d) delete(9): first line if cur is None: return. Does nothing. Why? You can't delete from nothing; returning is the correct no-op.

Verify: (a) output empty; (b) & (c) produce identical 9 -> null (length 1); (d) leaves list empty. Cell A never crashes. ✓

Example 4 — Cell D: insert in the middle (after position k)

Forecast: which node is "position 1", and what should the list read afterward?

1. Walk to node k=1. Start cur = head (node A, index 0). Loop for _ in range(1): one hop → cur = cur.next = node B (index 1). Why k hops? Starting at index 0, each cur = cur.next raises the index by 1, so k hops land you on node k.
2. Create: new = Node(X).
3. Wire new forward: new.next = cur.next. Node B's successor was C, so now X -> C. Why first? "Look before the door moves" — we must capture C before we overwrite B's arrow.
4. Redirect cur: cur.next = new, so B -> X.

Final: A -> B -> X -> C -> D -> null.

Verify: length 4 → 5. Traversal A, B, X, C, D. X sits between B and C exactly as required. Work done = k hops (here 1) + 2 constant pointer writes ⇒ $O(k)$. ✓

Example 5 — Cell E: delete the tail (last node)

Forecast: which node's next changes, and to what?

1. Head check: cur = head (node 10). Is cur.data == 30? No. So we don't touch head. Why check head first? Deleting the head needs head = head.next; deleting a non-head needs a prev. They're different mechanics, so we split them.
2. Set up the two-pointer walk: prev = head (node 10), cur = head.next (node 20). Why carry prev? A singly list can't look backward. To unlink cur, we make its predecessor skip it — so we must always hold that predecessor.
3. Walk. cur = 20: 20 != 30, advance prev = 20, cur = 30.
4. Match at cur = 30. Unlink: prev.next = cur.next. Here prev is node 20 and cur.next is None, so 20.next = None. Node 30 is now unreachable. Why this works at the tail? cur.next for the last node is None; copying None into prev.next correctly makes 20 the new last node.

Final: 10 -> 20 -> null.

Verify: length 3 → 2. Traversal 10, 20. New last node 20 has next = null. No crash, no orphaned live nodes. ✓

Example 6 — Cell D: delete a middle value

Forecast: which pointer gets rewired, and what does it point to afterward?

1. Head check: cur = head = node 1, 1 != 3. Not the head.
2. Two-pointer setup: prev = 1, cur = 2.
3. Walk: cur = 2, 2 != 3 → prev = 2, cur = 3.
4. Match: cur.data == 3. Unlink: prev.next = cur.next = 2.next = 4. Node 3 skipped. Why cur.next and not None? We must reconnect 2 to whatever came after 3 (namely 4), or we'd chop off the tail.

Final: 1 -> 2 -> 4 -> null.

Verify: length 4 → 3. Traversal 1, 2, 4. Node 2 now points straight to 4. ✓

Example 7 — Cell B & C: delete the head

Forecast: in each case, what is head afterward?

1. (i) Head check hits: cur = head, cur.data == 10. Do head = cur.next = node 20. Why no prev? The head has no predecessor. The external head pointer is the thing that leads into it, so we just move head forward. Result: 20 -> 30 -> null.
2. (ii) Single node: cur = head, cur.data == 99. head = cur.next = None. Why this empties the list? The lone node's next is None; moving head to None correctly leaves an empty list. Result: null (empty).

Verify: (i) length 3 → 2, traversal 20, 30. (ii) length 1 → 0, head is None is true. Both cases are handled by the same head-deletion branch. ✓

Example 8 — Cells F & G: value absent, and index out of range

Forecast: should either of these crash? What should each do?

1. (i) delete(100): head check 5 != 100. Then prev=5, cur=6. Walk: 6 != 100 → 7; 7 != 100 → cur = None. Loop while cur is not None ends. Function returns having changed nothing. Why safe? Walking off the end sets cur = None, the loop's stop condition — no null.data is ever read. The list is unchanged, which is correct: you can't delete what isn't there.
2. (ii) insert_after(9, "Z"): cur = head (index 0). Loop for _ in range(9). Hops: index 0→1→2, then cur.next of node 7 is None, so after the 3rd hop cur = None. On the next iteration the guard if cur is None: raise IndexError fires. Why raise instead of silently return? Inserting after a position that doesn't exist is a programmer error, not a valid no-op — loud failure prevents silent bugs.

Verify: (i) list stays 5, 6, 7 (length 3, unchanged). (ii) an IndexError is raised; list untouched. Both off-the-end cases are handled without dereferencing null. ✓

Example 9 — Cell H: the real-world word problem (music playlist)

Forecast: write the final order before working it.

1. "Play this next" = insert after position 0 (after Song1). Wire: new.next = Song1.next (= Song2), then Song1.next = new. List: Song1 -> SongX -> Song2 -> Song3 -> null. Cost: reach position 0 = 0 hops, so $O(1)$ here. Why $O(k)$ in general but $O(1)$ here? Insert-after is $O(k)$ where k is the position; k=0 means no walking.
2. "Add to end" = insert at tail. With only a head, walk to the node whose next is null (Song3), attach SongY. List: Song1 -> SongX -> Song2 -> Song3 -> SongY -> null. Cost: walk all $n$ nodes ⇒ $O(n)$. Why $O(n)$? No tail pointer is kept, so the last node must be found by walking (parent Section 3b).
3. Remove Song2 = delete by value (middle). Walk with prev/cur until cur = Song2 (predecessor is SongX), then SongX.next = Song2.next (= Song3). Final: Song1 -> SongX -> Song3 -> SongY -> null. Cost: $O(n)$.

Final playlist: Song1 -> SongX -> Song3 -> SongY -> null.

Verify: started length 3; +1 (SongX) +1 (SongY) −1 (Song2) = length 4. Order check: Song1, SongX, Song3, SongY. ✓

Flashcards