Collections: An Extended Example

public class LinkedListElement implements Element{
  private Object contents;
  private LinkedListElement next;

  public LinkedListElement( Object o ){
    this.contents = o;
    this.next = null;
  }

  public LinkedListElement insert ( Object o ) {
    if (this.next == null) {
      this.next = new LinkedListElement( o );
    } else {
      this.next = this.next.insert( o );  // this reassignment 
    }                                     // not strictly necessary
    return this;
  }

  public LinkedListElement delete ( Object o ) throws NoSuchElementException {
    if (this.contents == o) {
      return this.next;
    } else if (this.next == null) {
      throw new NoSuchElementException("Can't find " + o);
    } else {
      this.next = this.next.delete( o );
    }
    return this;
  }

  public boolean contains ( Object o ) {
    if (this.contents == o ) {
      return true; 
    } else if (this.next == null) {
      return false;
    } else {
      return this.next.contains( o );
    }
  }

  public boolean isEmpty () {
    return ( this.next == null );
  }
}

Interfaces

The following code defines the interface used by LinkedListElement. It is useful, e.g., for telling someone how to use LinkedListElement without showing them how LinkedListElement works. In fact, they don't even have to know that LinkedListElement is the interface implementation that we're using. All they need to know is that we're using something that implements Element. (We'll see more on how to use interfaces next week.)

public interface Element {

  public Element insert( Object o );

  public Element delete( Object o ) throws NoSuchElementException;

  public boolean contains( Object o );

  public boolean isEmpty();
}

Note that the method declarations don't have bodies. This is because they're not implementations. Interface methods just specify the method's signature. This is generally enough to be able to use an Element, but not enough to actually create one. (You can't use a construction expression with an interface!)

To use the interface we've defined, we need to implement it. Actually, the code above for LinkedListElement will do just fine, but we need to change it slightly to specify that it is an implementation of Element. We can do this by changing the first line of the class definition to

public class LinkedListElement implements Element {

When you implement an interface, you must provide definitions of each of the interface methods. The methods that you implement must have signatures matching those in the interface. (They'll need to be public, too.) In our case, the code we'd written for LinkedListElement mostly did this. However, our code returns LinkedListElement, not Element: the signatures don't exactly match. We'll need to fix this, too:

public class LinkedListElement implements Element{
  private Object contents;
  private LinkedListElement next;

  public LinkedListElement( Object o ){
    this.contents = o;
    this.next = null;
  }

  public Element insert ( Object o ) {
    if (this.next == null) {
      this.next = new LinkedListElement( o );
    } else {
      this.next = this.next.insert( o );  // this reassignment 
    }                                     // not strictly necessary
    return this;
  }

  public LinkedListElement delete ( Object o ) throws NoSuchElementException {
    if (this.contents == o) {
      return this.next;
    } else if (this.next == null) {
      throw new NoSuchElementException("Can't find " + o);
    } else {
      this.next = this.next.delete( o );
    }
    return this;
  }
}

Comments

The next piece of code is a rewrite of the Element interface with javadoc comments. These have two purposes. The first is the same as any other comment: to let someone reading the file know what the code means. The second (special) function is that comments beginning with /** can be read by a program called javadoc and used to produce nice html documentation. (Other comments, not read by javadoc, include //, which simply comments out the rest of the line, and /*, which comments out everything until the first */. Javadoc comments also match a closing */.

public interface Element {

  /**
   * @returns either self or new -- what should prev elt point to?
   */
  public Element insert( Object o );

  /**
   * @returns either self or next -- what should prev elt point to?
   */
  public Element delete( Object o ) throws NoSuchElementException;

  /**
   * @returns whether structure starting w/this elt contains o
   */
  public boolean contains( Object o );

  /**
   * @returns whether structure is empty
   */
  public boolean isEmpty();
}

Arrays

Java has a built-in collection type which allows you to access a uniform collection of elements by index. These are called arrays, and they're not as flexible as the lists described above.

An array declaration looks like this:

typeName[] name;

int[]    myNumbers;
Object[] myStuff;

Assuming that the myNumbers label has been stuck on a set of int-shoeboxes, you can find out how many with the expression

myNumbers.length

myNumbers[index]

myNumbers[3] = myNumbers[3] + myNumbers[2];myStuff[6].toString();

This course is a part of Lynn Andrea Stein's Rethinking CS101 project at the MIT AI Lab and the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology.