A sequence interface is mutable if it includes operations that modify the value of this. A typical interface for mutable sequences is the following:
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.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