Java Reference
In-Depth Information
3.2
The chain of desks provides an order for the desks. Suppose that first in the chain is the student who
arrived most recently. Written on this student's desk is the desk number of the student who arrived
just before. With one exception, everyone's desk references the desk of the student who arrived just
before. The exception is the person who arrived first. That person sits at the last desk, which does
not reference another desk.
The instructor knows the address of the first desk in the chain and so can ask questions of the
student at that first desk. Then, by looking at the address, or desk number, that is written on the
paper on the first desk, the instructor can locate the second desk in the chain and can question its
occupant. Continuing in this way, the instructor can visit every desk in the order in which they
appear in the chain. Ultimately, the instructor reaches the last desk in the chain, which references
no other desk. Note that the only way the instructor can locate the student in this last desk is to
begin at the first desk. Also note that the instructor can traverse this chain in only one order. In
our similar example in Chapter 2, the instructor in room A was able to ask questions of any stu-
dent in any order.
How did we form the chain of desks in the first place? Let's return to the time when room L was
empty and all available desks were in the hallway.
Suppose that Matt arrives first. He gets a desk from the hallway and enters the room. The
instructor notes Matt's desk number (address), and we leave the paper on his desk blank to indicate
that no other student has arrived. The room appears as in Figure 3-2.
FIGURE 3-2
One desk in the room
10
1
0
3.4
When the second student arrives, we write Matt's desk number on the new desk's paper and give
the instructor the number of the new desk to remember. Let's assume that the instructor can remem-
ber only one desk number at a time. The room now appears as in Figure 3-3. The new desk is at the
beginning of the chain.
When the third student arrives, we write the instructor's memorized desk number, which is that
of the desk at the beginning of the chain, on the new desk's paper. We then tell the instructor to
remember the number of the new desk, which is now at the beginning of the chain. The room now
appears as in Figure 3-4.
After all the students have arrived, the instructor knows only the desk number of the student
who arrived most recently. On that student's desk is the desk number of the student who arrived just
previously. In general, written on each student's desk is the number of the desk that belongs to the
previous student who arrived. Since Matt was the first student to arrive, the paper on his desk is still
blank. In Figures 3-1 through 3-4, desk 10 belongs to Matt.
