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

{

// add to beginning of chain:
Node newNode = new Node(newEntry);
newNode.next = firstNode; // make new node reference rest of chain
// (firstNode is null if chain is empty)

firstNode = newNode; // new node is at beginning of chain

numberOfEntries++;
return true ;
} // end add

3.13

An out-of-memory error. With a linked implementation, the bag cannot become full. Anytime
you add a new entry, you create a new node for that entry. Thus, the method add always returns
true. It is possible, however, for your program to use all of your computer's memory. If this
occurs, your request for a new node will cause the error OutOfMemoryError . You might interpret
this condition as a full bag, but an OutOfMemoryError is fatal, and the client will not have the
opportunity to react to it.

Note: Allocating memory
When you use the new operator, you create, or instantiate, an object. At that time, the Java
run-time environment allocates , or assigns, memory to the object. When you create a node
for a linked chain, we sometimes say that you have allocated the node.

3.14

The method toArray . The method toArray returns an array of the entries currently in a bag. By
implementing this method, we will be able to test whether the add method works before we com-
plete the rest of the class LinkedBag . To access the bag's entries, we need to access each node in a
chain, beginning with the first one. This action is called a traversal , and it is analogous to visiting
each desk in a chain of desks, as we described in Segment 3.2.
The data field firstNode contains a reference to the first node in the chain. That node contains a
reference to the second node in the chain, the second node contains a reference to the third node, and
so on. To traverse the chain, the method toArray needs a temporary, local variable currentNode to
reference each node in turn. When currentNode references the node whose data we want to access,
that data is at currentNode.data .
Initially, we want currentNode to reference the first node in the chain, so we set it to firstNode .
After accessing the data at currentNode.data , we move to the next node by executing
currentNode = currentNode.next;
We again access the data at currentNode.data and then move to the next node by executing
currentNode = currentNode.next;
once again. We continue in this manner until currentNode becomes null .
The following method toArray uses these ideas:

/** Retrieves all entries that are in this bag.
@return a newly allocated array of all the entries in the bag */
public T[] toArray()
{

// the cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Object[numberOfEntries]; // unchecked cast
int index = 0;