Java Reference
In-Depth Information
Question 5
If
currentNode
in the previous method
contains
becomes
null
, what value
does the method return when the bag is not empty?
Question 6
Trace the execution of the method
contains
when the bag is empty. What is
the result?
3.18
Earlier in this chapter, we used the analogy of a classroom to describe how to form a linked chain of
data. Available desks are in the hallway outside of the classroom. Each desk has a number (address)
stamped on its back and a blank piece of paper taped to its desktop. As students enter the room,
they take a desk from the hall. The number of another desk already in the room is written on the
new desk's piece of paper, and the instructor is given the new desk's number. In this way, the desks
are linked to one another, forming a chain of desks. As you saw in Figure 3-1, no desk references
the first desk in the chain, but the instructor knows its address. The last desk does not reference
another desk; its paper is blank.
Students who leave our classroom—room L—return their desks to the hall. Such desks can be
reassigned to other students who enter either room L or other rooms that share this hallway. Suppose
that you are a student in room L but you want to drop the course. If you simply move your desk to the
hallway, you will not actually remove yourself from the chain of desks in the room: Either another
desk or the instructor will still reference your desk. We need to disconnect your desk from the chain.
The details of how we do this depend on where your desk is in the chain. Here are the possible cases:
•
Case 1: Your desk is first in the chain of desks.
•
Case 2: Your desk is not first in the chain of desks.
3.19
Case 1.
Figure 3-8 illustrates Case 1 before we remove the first desk from the chain. The following
steps are necessary to remove the first desk:
1.
Locate the first desk by asking the instructor for its address.
2.
Give the address that is written on the first desk to the instructor. This is the address of the
second desk in the chain.
3.
Return the first desk to the hallway.
FIGURE 3-8
A chain of desks just prior to removing its first desk
