Java Reference
In-Depth Information
Chapter
2
Bag Implementations
That Use Arrays
Contents
Using a Fixed-Size Array to Implement the ADT Bag
An Analogy
A Group of Core Methods
Implementing the Core Methods
Testing the Core Methods
Implementing More Methods
Methods That Remove Entries
Using Array Resizing to Implement the ADT Bag
Resizing an Array
A New Implementation of a Bag
The Pros and Cons of Using an Array to Implement the ADT Bag
Prerequisites
Appendix D
Designing Classes
Chapter
1
Bags
Objectives
After studying this chapter, you should be able to
●
Implement the ADT bag by using a fixed-size array or an array that you expand dynamically
Discuss the advantages and disadvantages of the two implementations presented
●
Y
ou have seen several examples of how to use the ADT bag in a program. This
chapter presents two different ways—each involving an array—to implement a bag in
Java. When you use an array to organize data, the implementation is said to be
array
based
. You will see a completely different approach in the next chapter.
We begin by using an ordinary Java array to represent the entries in a bag. With
this implementation, your bag could become full, just as a grocery bag does. We then
offer another implementation that does not suffer from this problem. When you use
