Linked Representation

In the linked representation, a sequenceis a (reference to) an object, which is either an empty node, representing the empty sequence, or a cons node with a field of type T containing the first element of the sequence and a field of type Seq containing a pointer to the first node in the rest of the sequence. This data representation, which is often called a linked list, directly corresponds to the standard inductive definition of sequences. We defined this sequence representation in Section 1.12.3 as the class List, but that definition did not support all of operations listed above. The following modification of the List composite class hierarchy from Section 1.12.3 defines a linked representation for lists of objects; it includes all of the FinalSeq operations:

abstract class List implements FinalSeq {

  /* function methods */
  public Seq empty() { return EMPTY; }
  public Seq cons(Object first)  { return new Cons(first, this); }
  public abstract Object first();
  public abstract Seq rest();
  public abstract Object eltAt(int i);
  abstract public boolean isEmpty();

  /* mutators */
  public abstract Seq updateFirst(Object f);
  public abstract Seq updateRest(Seq r);

  abstract String toStringHelp();
  // List -> String without any parentheses and leading blanks

  static final Empty EMPTY = new Empty();

  private static class Empty extends List {

    /* constructor */
      private Empty() {}

    /* methods */
    public Object first() { 
      throw new IllegalArgumentException("first() applied to empty list");
    }
    public Seq rest() { 
      throw new IllegalArgumentException("rest() applied to empty list");
    }
    public int isEmpty() { return true; }

    public Seq updateFirst(Object o) {
      throw new IllegalArgumentException("updateFirst() applied to empty list");
    }
    public Seq updateRest(Seq s) {
      throw new IllegalArgumentException("updateFirst() applied to empty list");
    }
    public Object eltAt(int i) { 
      throw new IllegalArgumentException("out-of-bounds index in List.eltAt"); 
    }
    public Object execute(SeqVisitor v) { return v.forEmpty(this); }
    public String toString() { return "()"; }
    public String toStringHelp() { return ""; }
  }

  class Cons extends List {

    /* fields */
    private final Object first;
    private final List rest;

    /* constructor */
    Cons(Object f, List r) {
      first = f;
      rest = r;
    }

    /* methods */
    public Object first() { return first; }
    public Seq rest() { return rest; }
    public int isEmpty() { return false; }

    public Object eltAt(int i) { 
      if (0 == i) return first;
      else return rest.eltAt(i-1);
    }
    public Object execute(SeqVisitor v) { return v.forCons(this); }

    public Seq updateFirst(Object o) { return rest.cons(o); }
    public Seq updateRest(Seq r) { return r.cons(first); }

    public String toString() { return "(" + first + rest.toStringHelp() + ")"; }
    String toStringHelp() { return " " + first + rest.toStringHelp(); }
  }
}

The definition of the List class contains nested class definitions for the classes Empty and Cons. The static attribute identifies these classes as nested classes rather than inner classes. Nested classes are identical to conventional ``top-level'' classes except for two minor differences.

• First, nest classes have qualified names (of the form containing-class-name.nested-class-name).^2.3The full names for the classes Empty and Cons are List.Empty and List.Cons, respectively. Within the body of the List class, the unqualified names Empty and Cons are synonymous with the qualified names.
• Second, nested classes can be declared as private, making their names invisible outside the body of the containing class. Hence, the classe names List.Empty and List.Cons are not defined outside of the body of the List class. If we removed the private attribute for the Empty class above, then the classes

In contrast to instances of inner class, instances of nested classes do not have enclosing instances. Section 2.1.6 discusses nested and inner classes in more detail.

The for.. methods in the SeqVisitor interface all take a host argument of type Seq because the implementation is not constrained to use the composite pattern to represent immutable sequences. The following visitor class implements sequence concatenation:

class Append implements SeqVisitor {

  // returns sequence host || that
  /* fields */
  Seq that;

  /* constructor */
  Append(Seq t) { that = t; }

  /* methods */  
  public Object forEmpty(Seq host) { return that; }
  public Object forCons(Seq host) { 
    return host.updateRest((Seq) host.rest().execute(this));
  }

  public static void main(String[] args) {
    Seq s1 = List.EMPTY.cons("B").cons("A");
    Seq s2 = List.EMPTY.cons("C");
    System.out.println("s1 = " + s1);
    System.out.println("s2 = " + s2);
    System.out.println("s1 * s2 = " + s1.execute(new Append(s2)));
  }
}

The following figure shows a picture of linked list of integers.

In the figure, the nodes with two fields are Cons instances, and the crossed-box is an Empty instance. References (pointers) are represented by the heavy arrows. The reference fields in the cells are in fact memory addresses. In Java, these addresses are always interpreted as references to objects. Java only supports operations on references that are consistent with this abstraction, e.g. you cannot perform arithmetic on a reference. In lower-level languages like C and C++, references (pointers) can be manipulated as ordinary integers.

Finger Exercise 2.1.3.1 Write a SeqVisitor class to reverse a Seq. Test your code using DrJava. Hint: introduce a helper visitor with an extra parameter to accumulate the result.