Java Reference
In-Depth Information
U
sing an array to implement the ADT bag has both advantages and disadvantages, as you saw in
Chapter 2. An array has a fixed size, and so it can either become full or have several unused
elements. You can resize an array when it becomes full by moving its entries to a larger array.
Although resizing an array can provide as much space as a bag needs, you must move data each
time you expand the array.
This chapter introduces a data organization that uses memory only as needed for a new entry
and returns the unneeded memory to the system after an entry is removed. By linking data, this new
organization avoids moving data when adding or removing bag entries. These features make this
way of implementing a bag an important alternative to array-based approaches.
3.1
In Chapter 2, we used the analogy of a classroom to describe how data is stored in an array. Here
we use a classroom to show you another way to organize data.
Imagine an empty classroom—room L—that is assigned to a course. All available desks are in
the hallway. Any student who registers for the course receives a desk, takes it into the room, and
sits at it. Assume that the room can accommodate all of the desks that are in the hall.
Each desk in the hallway has a number stamped on its back. This number—called an
address
—
never changes and is not considered when desks are given to students. Thus, the room will eventu-
ally contain desks whose addresses are not sequential.
Now imagine that Jill is among 30 students who are seated in room L at exactly 30 desks.
Taped to each desktop is a piece of paper. As Jill entered the room, we wrote on her paper the desk
number (address) of another desk in the room. For example, the paper on Jill's desk might contain
the number 20. If her desk is desk 15, we say that desk 15
references
desk 20 and that desks 15 and
20 are
linked
. Since all of the desks are linked to one another in this way, we say that they form a
chain
of desks.
Figure 3-1 shows a chain of five desks. No desk references the first desk in the chain, but the
instructor knows its desk number, 22. Notice that the last desk in the chain does not reference
another desk; the piece of paper on this desk is blank.
VideoNote
Linked data
FIGURE 3-1
A chain of five desks
1
0
4
2
0
1
5
22
2
2
