5.1 Search in a list

Let us think about how to search for a value in a list.

• Base case 1: the list is empty. In this case, the list cannot possibly contain the value that we are looking for. Return false.
• Base case 2: the first value of the list is the value we are looking for. We can now return true.
• Recursive step: the list is not empty, and the first value does not match the value that we are looking for. In this case, we simply say “if the rest of the list has the value, then the list as a whole has the value.” In practice, we call the subroutine again, and return whatever the call returns.

The code to do this is as follows:

Line 3 checks to see if the list is empty or not. If the list is empty, we return false. Note that this condition is logical-anded with the rest, and C uses short-circuited boolean evaluation. This means that if this condition is false, the code does not bother to evaluate the other side of the && operator.

This means that we only get to evaluate line 4 iff the list is not empty. Line 4 checks to see if the first value of the list is the value that we are looking for. This condition is logical-ored with the next condition. This means that if this condition is true, then the code does not bother to check the other side of the || operator.

We only get to line 5 iff the list is not empty and the first value of this list does not match v. In that case, we call List_search again. However, this time, we pass List_getrest(pList) instead of pList. In other words, each time we perform the recursive call, the list is shortened by one node.