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

node. A second data field can track the number of entries in the bag, that is, the number of nodes in
the chain.

Listing 3-2 contains an outline of the class LinkedBag that implements the ADT bag and con-
tains the class Node as an inner class. Recall that Chapter 1 introduced the interface BagInterface
in Listing 1-1. It and the classes that implement it define a generic type for the objects in a bag. The
identifier T that we use for this generic type must match the one that we use within the class Node .

VideoNote

Beginning the class
LinkedBag

LISTING 3-2

An outline of the class LinkedBag

/**

A class of bags whose entries are stored in a chain of linked nodes.
The bag is never full.
@author Frank M. Carrano

*/
public class LinkedBag<T > implements BagInterface<T >
{

private Node firstNode; // reference to first node

private int numberOfEntries;

public LinkedBag()
{

firstNode = null ;
numberOfEntries = 0;
} // end default constructor

< Implementations of the public methods declared in BagInterface go here. >

. . .

private class Node // private inner class
{

< See Listing 3-1. >
} // end Node
} // end LinkedBag

The data field firstNode is the head reference of the chain of nodes. Just like the instructor who
knew the address of the first desk in the chain of desks, firstNode references the first node in the chain
of nodes. Another data field, numberOfEntries , records the number of entries in the current bag. This
number is also the number of nodes in the chain. Initially, a bag is empty, so the default constructor simply
initializes the data fields firstNode to null and numberOfEntries to zero.

Defining Some Core Methods
As we stated in the previous chapter, implementing and testing a core group of methods often is
advantageous when you write a class. Any method that adds an entry to a collection typically is a
core method for a class that implements a collection, such as a bag. Moreover, to verify that addi-
tions to a collection are made correctly, we need a way to look at the collection's entries. The
method toArray can serve this purpose, and so it also is a core method. Such was the case for the