Collections - Java Software Solutions: Foundations of Program Design - page 619

SELF-REVIEW QUESTIONS (see answers in Appendix N)
SR 13.1 What is a collection?
SR 13.2 Does the ArrayList class provide an abstract data type?
SR 13.3 Why are objects particularly well suited for implementing abstract
data types?

13.2 Dynamic Representations

An array is only one way in which a list can be represented. Arrays are limited
in one sense, because they have a fixed size throughout their existence. Sometimes
we don't know how big to make an array, because we don't know how much
information we will store. The ArrayList class handles this by creating a larger
array and copying everything over whenever necessary. This is not necessarily an
efficient implementation.
A dynamic data structure is implemented using links. Using ref-
erences as links between objects, we can create whatever type of
structure is appropriate for the situation. If implemented carefully,
the structure can be quite efficient to search and modify. Structures
created this way are considered to be dynamic, because their size is determined
dynamically, as they are used, and not by their declaration.

KEY CONCEPT
The size of a dynamic data structure
grows and shrinks as needed.

Dynamic Structures
Recall that the variable used to keep track of an object is actually a reference to
the object, meaning that it stores the address of the object. A declaration such as

House home = new House ("602 Greenbriar Court");

actually accomplishes two things: it declares home to be a reference to a House
object, and it instantiates an object of class House . Now consider an object that
contains a reference to another object of the same type. For example:

class Node
{
int info;
Node next;
}

Two objects of this class can be instantiated and chained together by having
the next reference of one Node object refer to the other Node object. The second