Java Reference
In-Depth Information
13.2
Adding a new student.
Imagine that we have already arranged the students in room A alphabeti-
cally by name. Suppose that a new student wants to join the students already in the room. Recall
that the 30 occupied desks are numbered sequentially from 0 to 29. Since 40 desks are in the room,
the desk numbered 30 is available. When the students were arranged by arrival time, we would sim-
ply have assigned the new student to desk 30. Since the students are now arranged alphabetically by
name, we must do more work.
Suppose that the new student belongs between the two students who occupy desks 10 and
11. That is, the new student's name is alphabetically between the names of the two students
who occupy desks 10 and 11. Since the desks' positions are fixed, the new student must
occupy desk 11. Before the new student can be seated, the student currently at desk 11 needs
to move to desk 12, as Figure 13-2 illustrates. This requirement, however, causes a chain
reaction: The student currently at desk 12 needs to move to desk 13, and so on. That is, each
student seated in desks 11 through 29 must move to the next higher-numbered desk. If only
one student moves at a time, the student in desk 29 must move to desk 30 before the student
in desk 28 can move to desk 29, and so on. As you can see, adding a new student requires
moving several other students. However, we do not disturb the students seated in the desks
that are before the new student's desk—desks 0 through 10 in our example.
FIGURE 13-2
Seating a new student between two existing students: At least
one other student must move
1
2
11
Ed
10
Carol
Ed, please move
back one desk.
Doug
Question 1
In the previous example, under what circumstance could you add a new stu-
dent alphabetically by name without moving any other student?
13.3
Removing a student.
Now imagine that the student in desk 5 of room A drops the course. The desk
stays in its fixed location within the room. If we still want students to sit in consecutively numbered
desks, several students will need to move. In fact, each student in desks 6 through 30 must move to
the next lower-numbered desk, beginning with the student in desk 6. That is, if only one student
moves at a time, the student in desk 6 must move to desk 5 before the student in desk 7 moves to
desk 6, and so on.
