Java Reference
In-Depth Information
Using an Array to Implement the ADT List
We begin with the classroom analogy used in Chapter 2 to describe how an array can represent a
bag, but this time we show how to represent a list. In doing so, we show how the add and remove
methods would work. Subsequently, we present a corresponding Java implementation for the list.
An Analogy
13.1
Let's recall the classroom, room A, that we used in Chapter 2 and picture it again in Figure 13-1.
The desks in the room are numbered sequentially, beginning with zero. An array is like this class-
room, and each desk is like one location within an array. Again, we will treat the desks as a one-
dimensional array and ignore that the desks are arranged in rows, as in a typical classroom.
FIGURE 13-1
A classroom that contains desks in fixed positions
3 9
3 8
3 1
3 7
3 0
2 3
3 6
2 9
2 2
1 5
3 5
2 8
2 1
1 4
3 4
7
2 7
2 0
1 3
3 3
6
2 6
1 9
1 2
3 2
5
2 5
1 8
1 1
4
2 4
1 7
1 0
3
1 6
9
2
8
1
0
Suppose that the first student who arrives at the classroom sits at desk 0; the second student sits
at desk 1, and so on. Eventually, 30 students occupy the desks numbered 0 through 29. They are
organized by arrival time. The instructor knows immediately who arrived first (that person is at
desk 0) and who arrived last (that person is at desk 29). Additionally, the instructor could ask for
the name of the student seated at any particular desk, just as a programmer can access any array ele-
ment directly. Thus, the instructor could ask for each student's name in order of arrival by polling
desks 0 through 29, or in reverse order by polling desks 29 through 0.
Instead of arranging the students in room A by arrival time, suppose that we arrange them
alphabetically by name. Doing so requires a sorting algorithm, such as the ones that Chapters 8 and
9 discuss. That is, the ADT list does not choose the order of its entries; the client must do so.
 
 
 
Search WWH ::




Custom Search