2.1.4 Mutable Sequences

A sequence interface is mutable if it includes operations that modify the value of this. A typical interface for mutable sequences is the following:

interface MutSeq {

  MutSeq empty();         
  // yields an object representing the empty sequence

  MutSeq cons(T newElt);  
  // returns new MutSeq with elts newElt, s[0], s[1], ..., s[n]

  MutSeq tail(); // returns new MutSeq with elts s[1], ..., s[n]
  T head();            // returns the element s[0]
  MutSeq eltAt(int i); // returns the element s[i]

  int length();           
  // yields the integer n+1, the number of elements in the sequence

  void MutSeq setEltAt(int i, T val);  // changes $s_i$ to val

As with immutable sequences, there are two basic implementation schemes for mutable sequences: linked and contiguous. Mutation complicates the implementation of linked representations, which we will examine in detail below.