Keywords: current

Next: 2.1.5 List Containers Up: 2.1.4 Mutable Sequences Previous: 2.1.4 Mutable Sequences

### 2.1.4.1 Singly-linked Mutable List Representation

The various linked mutable list representations that we will study are all derived from the standard linked representations for immutable sequences. A particularly simple approach to sequence mutation is to represent a mutable sequence as a variable `x` of immutable list type and implement mutation by assigning a new value to the variable, e.g.

      List x = empty();
      .
      .
      .
      x = cons(0,x);

But this approach fails to represent mutable lists as objects and to encapulate list mutation as an ordinary method. This representation cannot implement the `insert` method given above. In the list container representation, the `insert` operation modifies the program variable representing the mutable sequence, but variables are not objects! When we pass an immutable lists represented by an assignable variable as a method arguments, we can only pass the immutable list value to which the variable is bound.

Finger Exercise Try to write an insert method for mutable sequences represented by variables bound to immutable sequences. What goes wrong?