2.1.4 Mutable Sequences

A sequence implementation is mutable if it includes operations that modify the value of this. A class representing mutable sequences implements a subset of the following operations:

interface SeqObject extends Seq {

  void setFirst(T f);          // this = this.updateFirst(f) 
  void setRest(Seq r);         // this = this.updateRest(r) 
  void set(Seq v);             // this = v
  void setEltAt(int i, T val); // changes s[i] in this to val
  void insert(Object o);       // inserts o in front of s[0] in this 
  void remove();               // removes s[0] from this
}

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 examine in detail below.