Programming and Problem Solving with Java

(^534) | Array-Based Lists
public booleanisThere(String item)
// Returns true if item is in the list; false otherwise
{
int index = 0;
while(index < numItems && listItems[index].compareTo(item) != 0)
index++;
return(index < numItems);
}
This algorithm is called a sequentialor linear searchbecause we start at the beginning of
the list and look at each item in sequence. We halt the search as soon as we find the item
we are seeking (or when we reach the end of the list, concluding that the desired item is not
found in the list).
We can use this algorithm in any application requiring a list search. In the form shown,
it searches a list of Stringcomponents, but the algorithm works for any class that has a
compareTomethod.
Let’s look again at the heading for the operation that puts an item into the list.
public voidinsert(String item)
// Adds item to the list
// Assumption: item is not already in the list
Does anything in the documentation say where each new item should go? No, this is an un-
sorted list. Where we put each new item is up to the implementer. In this case, let’s put each
new item in the easiest place to reach: the next free slot in the array. Therefore, we can store
a new item into listItems[numItems]and then increment numItems.
This algorithm brings up a question: Do we need to check whether the list has room for
the new item? We have two choices. The insertmethod can test numItemsagainst
listItems.lengthand throw an exception if there isn’t room, or we can let the client code make
the test before calling insert. Our documentation is incomplete because it does not specify
what occurs in this situation. Let’s test for isFulland leave the list unchanged if the list is
full. The client can check before the call if he or she wishes to do something else in this sit-
uation.
This algorithm is so simple, we just go directly to code.
public voidinsert(String item)
// If the list is not full, puts item in the last position in the
// list; otherwise list is unchanged.
{
if (!isFull())
{
listItems[numItems] = item;
numItems++;
}
}
Deleting a component from a list consists of two parts: finding the item and removing it
from the list. We can use the same algorithm we used for isThereto look for the item. We know