ITPEC FE Subject B October 2024 Question 10

Inserting a node at a given position in a singly-linked list.

The procedure addNode(pos, val) inserts a new node at position pos. When pos = 1, the node is inserted at the head. Otherwise, the code traverses to the node just before the target position (prev) using a loop.

The two key lines for insertion after prev are:

1. newNode.next ← prev.next — point the new node to whatever prev currently points to
2. [blank] ← newNode — re-link prev to point to the new node

Since prev is the node right before the insertion point, we need prev.next ← newNode to complete the insertion. The blank is `prev.next`.

Why not others:
- (a) listHead — overwriting the head only makes sense when inserting at position 1 (handled in the if branch)
- (b) listHead.next — would break the list by redirecting the second link from head
- (c) listHead.next.next — arbitrary pointer deep in the list; unrelated to prev
- (d) prev — prev is a local variable, not a .next field; assigning to it doesn't change the list structure
- (f) prev.next.next — would skip the new node and modify the node after the insertion point

Key rule: To insert a node after prev in a singly-linked list, set newNode.next ← prev.next then prev.next ← newNode — always in that order.

AI-generated — may contain errors