Introduction: An Array-Based Data Structure

Prerequisites

• Class Definitions—The Fundamentals
• Class Definitions—More Details
• Arrays

Objectives

After completing this chapter, you should be able to:

• Describe the data organization known as a bag
• Use an array to implement a bag
• Identify a proposed class’s core methods
• Write a partial implementation of a class that includes definitions of its core methods
• Complete the definition of a class by using a strategy that tests each method as it is defined

Overview

The previous chapter introduced us to arrays, which are Java constructs for grouping either primitive values or objects of the same type. This chapter will begin to generalize the idea of grouping objects. In Java, a collection is an object that groups other objects and provides various services to its client. In particular, a typical collection enables a client to add, remove, retrieve, and query the objects it represents. Typically, the objects contained in a collection are related by their data type.

Various collections exist for different purposes. Their behaviors are specified abstractly and can differ in purpose according to the collection. Likewise, a specific collection can have several implementations as classes. Some implementations use arrays to hold the objects in the collection. This chapter will use much of the material in the previous chapter to define a nontrivial class that implements a particular collection. It will also give you some practical advice about developing the definition of a class. We will elaborate on this advice in the sequel to this course.

The Java code in this chapter uses the javadoc tags @param and @return, which the appendix, Documentation and Programming Style describes.