As written, each loop iteration in the LIST-SEARCH` procedure requires two tests: one for \(x \neq L.nil\) and one for \(x.key \neq k\). Show how to eliminate the test for \(x \neq L.nil\) in each iteration.

First of all, we can’t outright remove the condition or else the while loop may never terminate in cases where a node with value \(k\) is not found. Since we want the procedure to return \(L.nil\) when nothing is found we need simply make \(L.nil\) satisfy the one remaining condition.

In the chapter’s definition of sentinels it is mentioned that these objects still have all the attrbiutes of other objects on the list, so there is nothing stopping us from setting \(L.key = k\) thus making the sentinel object satisfy the one remaining condition guaranteeing that our loop will terminate by selecting the sentinel object unless it finds another object that holds value \(k\) first. Just in case it matters, let’s clear out this value once we are done searching:

REWRITTEN-LIST-SEARCH(L, k)`

1 x = L.nil.next

2 L.nil.key = k

3 while x.key != k:

4     x = x.next

5 L.nil.key = NIL

6 return x