Java Reference
In-Depth Information
//
Process the remaining students
while
(
students arrive
)
{
newDesk
represents the new student's desk
New student sits at
newDesk
Write the instructor's memorized address on
newDesk
Instructor memorizes the address of
newDesk
}
The previous section described how you can organize data by linking it together. This section expresses
these ideas in Java by beginning the implementation of the ADT bag.
We begin by defining the Java equivalent of a desk, called a
node
. Nodes are objects that you typi-
cally link together to form a data structure. Our particular nodes have two data fields each: one to
reference a piece of data—presently, an entry in a bag—and one to reference another node. An
entry in a bag is analogous to a person who sits at a desk. The reference to another node is analo-
gous to the address written on the paper that is on each desk.
The class that represents these nodes can have the following form:
class
Node
{
private
T data;
// entry in bag
private
Node next;
// link to next node
< Constructors >
. . .
< Accessor and mutator methods:
getData
,
setData
,
getNextNode
,
setNextNode
>
. . .
}
// end Node
3.7
Let's focus on the data fields. The field
data
contains a reference to one of the objects in the bag.
Sometimes we will call this field the
data portion
of the node. The data type of
data
is represented
here by the generic type
T
. Soon, you will see that
T
is the same generic type that the class of bags
will declare.
The field
next
contains a reference to another node. Notice that its data type is
Node
, which is
the class that we are currently defining! Such a circular definition might surprise you, but it is per-
fectly legal in Java. It also enables one node to reference another node, just as one desk references
another desk in our example. Notice that a desk does not reference a student in another desk. Like-
wise, a node does not reference the data in another node, but rather references the entire other node.
Sometimes we will call the field
next
the
link portion
of the node. Figure 3-5 illustrates two nodes
that are linked and contain references to objects in the bag.
FIGURE 3-5
Two linked nodes that each reference object data
Linked nodes
Objects in a bag
