Searching - Data Structures and Abstractions with Java - page 457

if (anEntry.equals(currentNode.getData()))
found = true ;
else
currentNode = currentNode.getNextNode();
} // end while
return found;
} // end contains

This implementation is like the one given in Segment 14.19 of Chapter 14.

A Recursive Sequential Search of an Unsorted Chain
18.19

When done recursively, a sequential search looks at the first entry in the list and, if it is not the
desired entry, searches the rest of the list. This recursive approach is the same regardless of
whether you implement the search at the client level by using only the list's ADT operations—as
you did in Question 4—or as a public method of an array-based implementation of the list—as we
did in Segment 18.6. We use the same approach for a linked implementation of the list, as follows.
How would you implement the step search the rest of the list when the list's entries are in a chain
of linked nodes? The iterative method contains that you saw in the previous segment uses a local
variable currentNode to move from node to node. A recursive method could not have currentNode
as a local variable, since currentNode would get reset to an initial value at each recursive call.
Instead, such a method needs currentNode as a formal parameter. But then we would have a method
whose parameter depends on the list's implementation, making it unsuitable as a public method. Just
as we did earlier in Segments 18.6 and 18.13, we would make this search method private and call it
from the public method contains .

18.20

The private recursive method search examines the list entry in the node that its parameter
currentNode references. If the entry is not the desired one, the method recursively calls itself
with an argument that references the next node in the chain. Thus, the method search has the
following implementation:

// Recursively searches a chain of nodes for desiredItem,
// beginning with the node that currentNode references.
private boolean search(Node currentNode, T desiredItem)
{

boolean found;
if (currentNode == null )
found = false ;
else if (desiredItem.equals(currentNode.getData()))
found = true ;
else
found = search(currentNode.getNextNode(), desiredItem);
return found;
} // end search
Now we write the public method contains as follows:

public boolean contains(T anEntry)
{

return search(firstNode, anEntry);
} // end contains
Notice that the call to the method search initializes the parameter currentNode to firstNode ,
much as an iterative method initializes its local variable currentNode to firstNode .