Summary

The size of an array cannot be changed, but the array-based structures discussed in this chapter are able to grow and shrink. They do this by maintaining a separate field indicating how many of the array positions are currently in use. This field also provides the index of the next available position. If all of the positions are in use, an array-based structure can be stretched by copying all of its elements into a new, larger array.

These techniques for stretching and shrinking are used in the ArrayStack class. The ArrayQueue class must do a little more work because, as elements are added to the back and removed from the front, the in-use portion of the array marches to the right. When it hits the right end of the array, it wraps around to the beginning. This is accomplished using the % operator.

The List interface describes a much more general data structure. It is implemented by the ArrayList class. In addition to providing basic methods for accessing particular elements and so on, a List can return an Iterator. An Iterator allows us to traverse the List, visiting each element.

Java's collections framework, in the java.util package, includes a List interface, an ArrayList class, a Stack class, and a Queue interface. We will see more interfaces and classes from this framework in later chapters.