A recursive list operation is easier to reason about when each call has a precise contract. We will remove all nodes whose value equals a target, preserving the order and identities of every remaining node.
Contract and ownership
Definition 10.2.1
(Contract of removeAll)
Input head is null or starts a finite, acyclic singly linked chain. Nodes have fields value and next. The caller gives the procedure exclusive permission to modify links and dispose of removed nodes. There must be no external pointer that will later be dereferenced to a removed node; surviving aliases observe the changed links. The list owns its nodes: dispose(p) releases exactly node p, not the suffix, and does not inspect or dispose p.next. Equality testing, link assignment and disposal each take constant time. The caller must replace its old head with the returned head; if a list object caches a tail or length, it must update that metadata separately.
Output: the head of the chain of the surviving nodes, in their original order, or null if none survives.
removeAll(p, target):
if p == null:
return null
rest = removeAll(p.next, target)
if p.value == target:
dispose(p) // rest remains live
return rest
p.next = rest
return p
The recursive call processes the original suffix before deciding what to return for p. If p is removed, its caller receives rest; otherwise p.next is repaired to point at the filtered suffix. In particular, never write through p after disposing it. Because disposal does not traverse p.next, the old link inside a removed p need not be cleared before disposal. A language with recursive destructors or shared ownership requires a different disposal policy; this pseudocode does not silently assume one.
Concept lensAlgorithmic
The same filter as one forward pass
The same result comes from a single left-to-right pass that remembers the last survivor. Save p.next, then either dispose p or attach it after the last survivor (becoming the head if there is none). The returned chain and the set of disposed nodes are the same, but disposal now happens front to back and the extra space is constant.
Common mistake
(Keeping the old head after the call)
Take A(2) -> B(5) -> null with target . The call returns B and disposes A. If the caller keeps using its variable head, still equal to A, it reads a disposed node. The head variable is not changed by the call, because the procedure returns a new head rather than assigning to the caller's variable. The caller must write head = removeAll(head, 2).
Common mistake
(Forgetting to relink a survivor)
If the survivor branch returned p without the assignment p.next = rest, then in B(5) -> C(2) -> D(7) with target the node B would still point to the disposed node C, although C was removed. The assignment p.next = rest is what splices out the removed nodes that follow p, and it must be executed on every survivor.
Why it works
Theorem 10.2.2
(Correctness and cost of recursive removal)
Let head be null or the head of a finite, acyclic chain of nodes. Then removeAll(head, target) returns the head of the chain consisting of exactly the nodes whose value differs from target, in their original order and with their original identities. Each removed node is disposed exactly once, and no surviving node is disposed. The call takes time and stack space, and allocates no node.
Proof
(Induction on the length of the chain)
Each call on a nonempty chain recurses on a chain one node shorter. The length is a nonnegative integer, so eventually the null base case is reached. For correctness, use induction on the original length. The empty result contains exactly the required nodes in order. Assume the recursive call returns the original suffix with exactly its matching nodes removed and its surviving identities in their original order. If p matches, disposing it and returning that suffix removes exactly the required nodes. Otherwise linking p to that suffix keeps p first, followed by the surviving suffix in its original order. Thus the contract holds for the whole chain. Each removed node is disposed exactly once and no survivor is disposed.
With n original nodes, there are n nonempty calls and one base call, each doing constant work: time is , and the call stack uses space. No new list nodes are allocated. This stack bound matters even when every node is removed; recursion has already descended before disposal begins.
Proof X-ray
What the induction hypothesis must say
The hypothesis is stated about the suffix as a chain of its own: the call on p.next returns the head of that suffix with its matching nodes removed. The proof uses this twice. When p matches, the answer is that returned head, so nothing else needs repair. When p survives, only p's own link is changed, and it is set to the returned head, so the survivors stay in order. The recursion happens before p is touched, so p.next is read while p is still live. The step to a shorter chain needs the chain to be finite and acyclic: that is what makes the length decrease and the base case reachable, as the counterexample below shows.
Counterexample mode
A cyclic chain has no base case
Drop the hypothesis that the chain is acyclic. Let A(1) -> B(2) -> A with B.next pointing back to A, and call removeAll(A, 7). The call on A recurses on B, which recurses on A again, and so on: the calls never reach null, no call ever returns, and the stack grows until it overflows. The length argument fails because the "suffix" after A is not shorter. The contract requires a finite acyclic chain; a list that may contain a cycle must first be checked, for example with Floyd's method.
Practice: trace returns
Worked example 10.2.3
(Return values during unwinding)
Distinct nodes A(2) -> B(5) -> C(2) -> D(7) -> null form a list. Apply removeAll(head, 2). We list the return value of each nonempty call during unwinding, the nodes disposed, and the final chain, and say why the caller must assign the return value to its head.
Starting at the end, D survives, sets D.next = null, and returns D. C matches, is disposed, and returns D. B survives, sets B.next = D, and returns B. A matches, is disposed, and returns B. The resulting chain is B(5) -> D(7) -> null, in the original relative order; A and C are disposed once each. The caller's old head was A, which is no longer live, so retaining it would leave a dangling pointer. Assigning the returned B supplies the correct head. A cached tail remains D here, but it is not generally safe to assume that the old tail survives.
Worked example 10.2.4
(Consecutive matches at the front)
Apply removeAll(head, 3) to X(3) -> Y(3) -> Z(1) -> null. The innermost nonempty call is on Z: it survives, sets Z.next = null and returns Z. Y matches, is disposed, and returns Z. X matches, is disposed, and returns Z. The returned head is Z, and the final chain is Z(1) -> null. Two adjacent matches cause no difficulty, because each matching node simply forwards the head of its filtered suffix.
Practice: edge cases and metadata
Worked example 10.2.5
(Metadata when every node, or none, is removed)
A list object stores head, tail, and length. Its nodes are P(4) -> Q(4) -> R(4) -> null, with length 3. Remove target 4 using the procedure. We give the returned head and all metadata after the caller repairs it. Then we apply the procedure to U(1) -> V(3) -> null with target 4, give the result and explain its cost, and describe a safe general way to repair the metadata without using a disposed pointer.
In the first call R, then Q, then P are disposed as recursion unwinds; each call returns null. The returned head and corrected tail are null and the corrected length is 0. For the second list, both nodes survive in the same order and with the same identities; the returned head is U, the tail is V, and length is 2. The procedure still visits both nodes, so it takes time and stack space even with no matches. In general, first assign the returned head. Traverse the returned live chain, counting nodes and remembering the last one; use null as the tail if the chain is empty. This adds time and extra iterative space, leaving total time . Never inspect the old head or tail after the call unless their survival is independently known.
Exercises with solutions
Quick check
(Apply removeAll(head, 5) to P(5) -> Q(5) -> R(8) -> S(5) -> null. Give the return value of each nonempty call during unwinding, the disposed nodes and the final chain.)
Solution · Answer
The calls unwind from the end. S matches, is disposed and returns null. R survives, sets R.next = null and returns R. Q matches, is disposed and returns R. P matches, is disposed and returns R. The disposed nodes are S, Q and P, and the final chain is R(8) -> null, with returned head R.
Quick check
(In the recursive procedure, why is the recursive call made before dispose(p) rather than after it?)
Solution · Answer
The call reads p.next, and that read must happen while p is still live. After dispose(p) the node must not be dereferenced, so reading p.next afterwards would use a disposed node. Making the call first also means rest is already available when p is disposed, so p can be replaced by rest in one step.
Quick check
(A list of nodes all have the target value. How many calls does removeAll make, and what resource may run out in a language with a limited recursion depth?)
Solution · Answer
There are nonempty calls and one base call, so calls, all on the stack at once at the deepest point, because disposal only starts as the recursion unwinds. The call stack, with space, may overflow even though no node is kept. An iterative version with a pointer to the previous survivor uses extra space.