A Bag Implementation That Links Data - Data Structures and Abstractions with Java - page 62

3.8

The rest of the definition of the class Node is uneventful. Constructors to initialize the node are use-
ful, and since the data fields are private, methods to access and alter their contents are provided.
But are they really necessary? If we intend Node to be for public use, like our other classes, such
methods are necessary; however, Node is a detail of this implementation of the ADT bag that should
be hidden from the bag's client. One way to hide Node from the world is to define it within a pack-
age that also contains the class that implements the bag. Another way—the way we will use here—
is to define Node within an outer class , the one that implements the bag. Because of its placement
within another class, Node is an example of an inner class . We declare it to be private. An outer
class can access the data fields of an inner class directly by name without the need for accessor and
mutator methods. Thus, we write the simpler definition of Node shown in Listing 3-1.

LISTING 3-1

The private inner class Node

private class Node
{

private T data; // entry in bag
private Node next; // link to next node

private Node(T dataPortion)
{

this (dataPortion, null );
} // end constructor

private Node(T dataPortion, Node nextNode)
{

data = dataPortion;
next = nextNode;
} // end constructor
} // end Node

We did not include a default constructor because we will not need one.
Because Node will be an inner class, the generic type T will be the same as the generic type
declared by the outer class that contains Node . Thus, we do not write < T > after Node . If, however,
Node was not an inner class but instead had package access or public access, you would write
Node < T > . In that case, Node would also require set and get methods for its data fields.

Note: Terminology
A nested class is defined entirely within another class definition. Nested classes can be static,
although we will not encounter any in this topic. An inner class is a nested class that is not
static. An outer class, or enclosing class , contains a nested class. A top-level class is one that
is not nested.

An Outline of the Class LinkedBag
3.9

For this implementation of the ADT bag, we will use a chain of linked nodes to contain the bag's
entries. In our earlier classroom example, the instructor remembered the address of the first desk in
a chain of desks. Similarly, our implementation must “remember” the address of the first node in
the chain of nodes. We use a data field called the head reference to record a reference to this first