2.1 Sequences

The first data structures that we will discuss are the common representations for sequences of elements. A sequence is an ordered collection $s_0, s_1, s_2, ..., s_n$, $n>=0$ of data objects drawn from some base data type $D$. 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 operations as Java interfaces.

We have already used a common representation for sequences, namely functional lists, in many of our examples of functional programming in the preceding chapter. Before we explore general representations for sequences, we need to discuss a particular formulation of sequences called arrays, which are built-in to Java as they are in nearly all other programming languages.