2.1.4.1 Singly-linked Mutable List Representation

This mutable list representation is based on the linked representation for immutable sequences. A particularly simple approach to sequence mutation is to represent mutable sequences simply as variables of of immutable list type and implement mutation by ordinary assignment:

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

but this approach is very restrictive. When we use variables representing mutable sequences as method arguments, we only pass the immutable values of these variables, not the variables (memory cells that can be updated) themselves. A better approach is to define a container class with a field pointing to an immutable sequence. Then we can update the mutable sequence by modifying the contents of the field in the container object. For example, suppose we have a class FunList that defines a list representation for immutable sequences. A reasonable container class that uses FunList is

class MutList {
  FunList value;
  List() {
    value = new Empty();
  }

  void insert(Object o) {
    value = new Cons(o, value);
  }

  Object remove() {
    Object result = List.first;
    value = value.rest;
    return result;
  }
}

The variable holding the FunList instance is now wrapped inside an instance of the List class. A method that accepts List instances as arguments can now modify them.

The insert method modifies the list it is invoked on, so there is no need for it to return a value and its return type is set to void. Mutator methods often have the return type void because they embody commands that modify objects rather than functions that compute new values based on the value of this. The mutator method remove in the List class departs from this convention by returning the element that was formerly stored at the front of the list. If a separate access method

  Object firstElement() {
    return List.first;
  }

were provided, a simpler remove method would suffice:

  void remove() {
    value = value.rest;
  }

The efficient operations for this form of mutable lists correspond to the efficient operations on the underlying FunList class: adding and removing elements at the front of the list. Mutable lists in which elements can only added or removed at the front are called stacks or LIFO lists (LIFO="last in, first out").

The preceding implementation of mutable lists is not effective if the mutable list interface includes an operation for inserting elements at the rear of a list. To support such an insert operation in the List class above, the corresponding method would have to construct a new copy of the entire list starting with a singleton FunList value containing the new list element.

If a list implementation makes it cheap to add elements to the back of the list, and remove them from the front, then it can be used as a queue, or a FIFO list (FIFO="first in, first out").