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

Moreover, you can remove and recycle nodes that are no longer needed. Although you can resize an
array to allow a bag to grow in size—as the previous chapter describes—each time a larger array is
necessary, you must copy the entries from the full array to the new array. No such copying is
required when you use a chain.
Adding a new entry to the end of an array or to the beginning of a chain are both relatively sim-
ple tasks. Both operations are fast, unless the array needs to be resized. Likewise, removing the
entry at the end of an array or the beginning of a chain takes about the same effort. However,
removing a specific entry requires a search of the array or chain.
Lastly, a chain requires more memory than an array of the same length. Although both data
structures contain references to data objects, each node in a chain also contains a reference to
another node. However, an array is often larger than necessary, so memory is wasted. A chain uses
memory only as needed.

Question 13 Compare the efforts made by the contains methods in the classes LinkedBag
in this chapter and ResizableArrayBag in Chapter 2. Does one take more time to perform its
task? Explain.

C HAPTER S UMMARY

•

You can form a chain of linked data by using objects called nodes. Each node has two parts. One part con-
tains a reference to a data object, and the second part references the next node in the chain. The last node,
however, references no other node and contains null . A head reference external to the chain references the
first node.

• You can add a node to the beginning of a chain of linked nodes by changing two references: the one within

the node to be added and the chain's head reference.

• You can remove the first node in a chain of linked nodes by setting the chain's head reference to the refer-

ence within the first node.

• Locating a particular node in a chain of linked nodes requires a traversal of the chain. Beginning at the first

node, you move from node to node sequentially until you reach the desired node.

• The class Node can be an inner class of LinkedBag or a class within a package that contains LinkedBag . In

the latter case, Node must define set and get methods to provide access to its data fields.

P ROGRAMMING T IP

•

If ref is a reference to a node in a chain, be sure that ref is not null before you use it to access ref.data or
ref.next .

E XERCISES

1.

Add a constructor to the class LinkedBag that creates a bag from a given array of objects.

2.

Consider the definition of LinkedBag 's add method that appears in Segment 3.12. Interchange the second and
third statements in the method's body, as follows:
firstNode = newNode;
newNode.next = firstNode;

a. What is displayed by the following statements in a client of the modified LinkedBag ?
BagInterface<String> myBag = new LinkedBag<String>();
myBag.add("30");