By convention, linked representations of sequences are called lists. This representation of sequences is so pervasive that the terms sequence and lst are often used interchangeably (conflating the abstraction and the implementation). A particularly important distinction between sequence interfaces is whether or not an interface includes operations that mutate (destructively modify) the object this. For example, if a sequence object x contains the Strings "Corky" and "Matthias", does any operation on the object x permit the contents of x to be modified, i.e., changing, adding, or subtracting elements? Operations on x that construct new sequences that incorporate the contents of x are not mutators because the object x is left unchanged.
Immutable data types are easier to define, to use, and to implement than mutable data types, but they they have two important limitations. First, they do not support some computations efficiently. Second, object mutation plays a critical role in the natural modeling of some computational problems. The functional model of computation that we studied in Chapter 1 is exclusively concerned with immutable data. The term ``functional list'' is synonymous with ``immutable list''.
We will focus first on immutable sequences and their representations. Then we will investigate what adjustments must be made to support mutation.