Keywords: current

Next: 2.1.3.2 Contiguous Representation Up: 2.1.3 Immutable Sequences Previous: 2.1.3 Immutable Sequences

### 2.1.3.1 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.9.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.9.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.4The 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 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.

Next: 2.1.3.2 Contiguous Representation Up: 2.1.3 Immutable Sequences Previous: 2.1.3 Immutable Sequences