Noesis
3.2.2 · D5Linear Data Structures

Question bank — Linked list — singly - node structure, traversal, insert head - tail - middle, delete

1,895 words9 min read↑ Back to topic

A quick vocabulary refresh so nothing below uses a word you haven't pinned down:

  • node — a box holding data (the value) and next (a pointer to the following box, or null at the end).
  • head — the single external pointer to the first node; the only door into the list.
  • null / None — the special "there is nothing here" address; the last node's next is null.
  • traverse — walk node-to-node following next until you hit null.
Figure — Linked list — singly - node structure, traversal, insert head - tail - middle, delete

True or false — justify

Cloze the verdict word, then defend it.

A singly linked list can reach node #5 without touching nodes #0–#4.
False. A node only knows its successor, so the only route to #5 is to hop through every earlier node from head — there is no base + i*size shortcut like an array has.
Losing the head pointer while keeping all the nodes still lets you rebuild the list.
False. Nothing else points to the first node, so once head is gone the whole chain is unreachable and gets garbage-collected — the nodes still exist for an instant but you have no address to find them.
Inserting at the head is regardless of how long the list already is.
True. You only rewire two pointers (new.next = head, then head = new); the length never enters the work, so it stays constant-time — see Big-O Notation.
Inserting at the tail is always for any linked list.
False. It is only when you have head alone and must walk to find null. Keep a tail pointer (or use a Doubly Linked List) and tail-insert becomes .
The empty list and a one-node list behave identically for insertion code.
False. Empty means head is None, so any walk that starts at head immediately dereferences None. A one-node list has a real node to walk from. The empty case almost always needs its own branch.
next = null and "node does not exist" mean the same thing.
False. next = null is a real, existing last node saying "nothing after me." A non-existent node is null/None sitting where a node reference should be. The last node is present; its next is what's absent.
Deleting the head node needs a prev pointer just like deleting a middle node.
False. The head has no predecessor inside the list; you delete it by moving the door: head = head.next. Only interior deletions need a trailing prev.
After prev.next = cur.next, the node cur is instantly erased from memory.
False. It becomes unreachable, not instantly freed. In garbage-collected languages the runtime reclaims it later; in manual-memory languages you must free/delete it yourself or you leak it.

Spot the error

Each line has a subtle bug; the reveal says what breaks and why. The figure below shows the two insertion traps as before → after arrow pictures — glance at it as you read the first two rows.

Figure — Linked list — singly - node structure, traversal, insert head - tail - middle, delete
cur = head; while cur.next is not None: print(cur.data); cur = cur.next — visit all nodes.
The loop stops one node early (it never prints the final node whose next is null) and crashes on an empty list because None.next is an error. Loop on while cur is not None instead.
insert_head: writing head = new first, then new.next = head.
After head = new, the variable head already points to new, so new.next = head makes the new node point to itself (top row of the figure). The old chain is lost and you've built a one-node loop. Always wire new.next = head before moving the door.
insert_after(p): writing p.next = new first, then new.next = p.next.
The first line overwrites p.next, so the second line copies the new value back — new.next ends up pointing to new itself (bottom row of the figure). Everything that used to follow p is orphaned. Wire the new node's forward arrow first.
insert_tail with no empty-list check: cur = head; while cur.next ....
If the list is empty, cur = head is None and cur.next throws immediately. You must special-case head is None by setting head = new.
Delete-by-value that advances only cur (never carries prev).
When you find cur, you have no handle on the node before it, and a singly list can't look backward — so you cannot perform prev.next = cur.next. You must drag a trailing prev one step behind cur.
Inside the delete loop, writing cur = cur.next but forgetting prev = cur.
prev freezes on the head forever while cur marches ahead, so prev.next = cur.next unlinks the wrong span and corrupts the chain. Advance both pointers each iteration.
insert_after(k) loops for _ in range(k) but never checks cur is None inside.
If k exceeds the list length, cur becomes None mid-loop and the next cur = cur.next (or cur.next = new) dereferences None. Guard with an out-of-range check before hopping.

Why questions

The delete figure below shows the correct prev/cur skip so these "why" answers have a picture to point at.

Figure — Linked list — singly - node structure, traversal, insert head - tail - middle, delete
Why does an array give index access but a linked list gives ?
An array lives in one contiguous block, so item i is at base + i*size — pure arithmetic. Linked-list nodes are scattered; each only knows its successor, so reaching index i costs i pointer-follows.
Why must you always wire the new node's next before redirecting the incoming pointer?
The incoming pointer (head or prev.next) is your only reference to the rest of the chain. Overwrite it first and you've thrown away the address the new node still needs to grab. Copy-then-redirect preserves it.
Why does a singly list need a prev pointer for interior deletion but not for insertion-after?
Deletion must edit the predecessor's next to skip the target (see the prev.next arrow in the figure), and you can't travel backward. Insertion-after already stands on the predecessor p, so you edit p.next directly — no separate prev needed.
Why is head special enough to justify branches in both insert and delete code?
head is the one pointer with no node in front of it. Every "predecessor-based" trick fails for the first node, so head-insertion and head-deletion move the door directly instead of splicing between two nodes.
Why can traversal use only extra space even though it visits nodes?
Visiting is not the same as storing. One walking pointer cur is reused for every hop; you never keep more than a single reference at a time, so extra memory stays constant while time grows with .
Why does re-pointing two arrows beat an array's shift-everything insert?
An array insert must physically move all elements after the slot to keep contiguity — copies. A linked list just changes two next fields; the scattered nodes don't move, so the structural edit is once you're at the spot.
Why is "search then insert-after" still even though the splice itself is ?
Finding the target position requires walking up to nodes, which is in the worst case. The splice can't rescue the walk that precedes it — total cost is dominated by the search.

Edge cases

Deleting a value that isn't in the list.
The cur walk reaches null without ever matching, the loop ends, and the function returns having changed nothing — correct behaviour, but only if your loop condition is while cur is not None.
Deleting from an empty list.
cur = head is None, so you must return immediately. Skipping this check makes cur.data dereference None and crash.
Inserting at the tail of an empty list.
There is no node to attach to, so the while cur.next walk can't run. The empty branch sets head = new, making the new node both first and last.
Deleting the only node in a one-node list.
It's a head deletion: head = head.next, which sets head = None. The list correctly becomes empty; no prev logic is involved.
insert_after(k) when k points at the current last node.
cur.next is null, so new.next = cur.next makes new the new tail (pointing to null) and cur.next = new attaches it — an effective tail insert with no special code needed.
Deleting when the first two nodes both hold the target value (delete-first-match).
Only the head node is removed (head = head.next); the loop never runs. The second matching node survives because "first match" stops at the earliest occurrence.
A list where the last node's next was accidentally left pointing back into the list (a cycle).
Traversal never sees null, so while cur is not None loops forever. Singly lists assume a null-terminated chain; a stray back-pointer breaks that invariant — this is why cycle detection matters for structures like a Queue using Linked List or Stack using Linked List.