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

class ArrayBag in the previous chapter, and it is true of our present class LinkedBag . Before we do
anything else, let's define the bag's methods add and toArray .

3.10

The method add : Beginning a chain of nodes. In Segment 3.3, the room was empty when the first
student arrived. As we noted in Segment 3.5, we took the following steps to begin a chain of desks:
newDesk represents the new student's desk
New student sits at newDesk
Instructor memorizes the address of newDesk

Here are the analogous steps that the method add must take to add the first entry to an initially
empty bag. Note that the desk in the previous pseudocode is analogous to a node defined within
LinkedBag , the student is analogous to a bag entry—that is, the data within the node—and the
instructor is analogous to firstNode .
newNode references a new instance of Node
Place data in newNode
firstNode = address of newNode

Thus, when the method add adds the first entry to an initially empty bag, it creates a new node and
makes it a one-node chain.
In Java, these steps appear as follows, where newEntry references the entry to be added to the bag:

Node newNode = new Node(newEntry);
firstNode = newNode;
Figure 3-6 illustrates these two steps. Part a of this figure shows the empty chain and the node cre-
ated by the first statement. Part b shows the result of the second statement. Notice that in Part b ,
both firstNode and newNode reference the same node. After the insertion of the new node is com-
plete, only firstNode should reference it. We could set newNode to null , but as you will see
shortly, newNode is a local variable of the method add . As such, newNode will not exist after add
ends its execution. The same is true of the parameter newEntry , which behaves like a local variable.

FIGURE 3-6

(a) An empty chain and a new node; (b) after adding a new node
to a chain that was empty

(a) (b)

firstNode firstNode

newNode newNode

newEntry newEntry

3.11

The method add : Adding to the chain of nodes. Just as we added new desks to the beginning of
an existing chain in Segment 3.5, the method add will add new nodes to the beginning of its chain.
In the context of desks in a room, the necessary steps are
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