Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 97

for(L.moveToStart();L.currPos()<L.length();L.next()){
it=L.getValue();
doSomething(it);

}

In this example, each element of the list in turn is stored in it , and passed to the
doSomething function. The loop terminates when the current position reaches
the end of the list.
The list class declaration presented here is just one of many possible interpreta-
tions for lists. Figure 4.1 provides most of the operations that one naturally expects
to perform on lists and serves to illustrate the issues relevant to implementing the
list data structure. As an example of using the list ADT, we can create a function
to return true if there is an occurrence of a given integer in the list, and false
otherwise. The find method needs no knowledge about the specific list imple-
mentation, just the list ADT.

/ ** @returnTrueifkisinlistL,falseotherwise * /
publicstaticbooleanfind(List<Integer>L,intk){
for(L.moveToStart();L.currPos()<L.length();L.next())
if(k==L.getValue())returntrue; //Foundk
returnfalse; //knotfound

}

While this implementation for find could be written as a generic with respect
to the element type, it would still be limited in its ability to handle different data
types stored on the list. In particular, it only works when the description for the
object being searched for ( k in the function) is of the same type as the objects
themselves, and that can meaningfully be compared when using the == comparison
operator. A more typical situation is that we are searching for a record that contains
a key field who's value matches k . Similar functions to find and return a composite
element based on a key value can be created using the list implementation, but to
do so requires some agreement between the list ADT and the find function on the
concept of a key, and on how keys may be compared. This topic will be discussed
in Section 4.4.

4.1.1 Array-Based List Implementation
There are two standard approaches to implementing lists, the array-based list, and
the linked list. This section discusses the array-based approach. The linked list is
presented in Section 4.1.2. Time and space efficiency comparisons for the two are
discussed in Section 4.1.3.
Figure 4.2 shows the array-based list implementation, named AList . AList
inherits from abstract class List and so must implement all of the member func-
tions of List .
Class AList 's private portion contains the data members for the array-based
list. These include listArray , the array which holds the list elements. Because