The first data structures that we will discuss are the common representations for sequences of elements. A sequence is an ordered collection d0, d1, d2, ..., dn, n>=0 of data objects drawn from some base data type D. For example, the names of all of the students in a class in alphabetic order is a sequence of String objects. Similarly, the numeric grades earned by each students on class assignments is a sequence of int values (or Integer objects).
Sequence representations can be classified based on the set of operations that they support. In Java, it is convenient to describe these various sets of sequence operations using Java interfaces. If we include all of the primitive operations for a given formulation of sequences in an interface, then we can freely change the implementation without affecting client programs that use the sequence interface.
We have already used the a common representation for sequences, namely functional lists, in the functional programming examples in the preceding chapter. Before we explore general representations for sequences, we need to discuss arrays, which are built into Java and nearly all other programming languages.