CS231 lecture notes, Fall 1998
Week 2, Wednesday

Reading Standish Chapter 3.1 to 3.4

Version 1 of insertNewSecondNode

Looking at this method after class on Monday, Mike convinced me that
it is wrong, that it actually adds the new node at the beginning of
the list, which just goes to show you that programs using references
can be difficult to read.

That's why the pointer-arrow diagrams are useful.

  public void insertNewSecondNode (String airport)
  {
    if (length == 0) return;

    ListNode newNode = new ListNode ();
    newNode.airport = airport;
    newNode.next = head.next;
    head.next = newNode;
    length++;
  }


Shorter version:

  public void insertNewSecondNode (String airport)
  {
    if (length == 0) return;

    head.next = new ListNode (airport, head.next);
    length++;
  }

Not so easy to read, but it is sweet.

Develop insertNewFirstNode as in-class-exercise.

Long version:

  public void insertNewFirstNode (String airport)
  {
    ListNode newNode = new ListNode ();
    newNode.airport = airport;
    newNode.next = head;
    head = newNode;
    length++;
  }

Do we need to check for the empty list?

Short version:

  public void insertNewFirstNode (String airport)
  {
    head = new ListNode (airport, head);
    length++;
  }

Gotta like that.

Break.

Traversing a list: an idiom very much like traversing an array,
that we did so much of last semester.

  public void print () {
    ListNode node;

    // remember that things that get printed get buffered until
    // we print a newline or use println
    System.out.print ("(");

    // start at the beginning of the list
    node = head;

    // traverse the list, printing each element
    while (node != null) {
      System.out.print (node.airport);
      node = node.next;
      if (node != null) {
	System.out.print (", ");
      }
    }

1) use a temporary ListNode reference to point to the elements of the
   list in succession

2) safer to use null to detect end of list, rather than assume length
   field is right  (if so, why have a length field at all?)

3) can we prove that this code will not produce a null-pointer
   exception under any circumstances?

4) can we prove that this code will terminate?

5) what are the requirements for a well-formed list?

   a) List object must be non-null

      (the empty list is represented by a List object with the
      head field equal to null, not by a null reference)

   b) length field must be equal to the number of ListNode objects
      (would less than be ok?)

   c) should we require no loops, or is that a legitimate representation
      of an infinite (albeit repeating) list?

Big point: in order to prove the correctness of a method, we generally
    need to make some assumptions about the inputs.  These assumptions
    are called ***preconditions***.

Generally good style to check the preconditions at the beginning of
the method.

We've already seen one example:

  public void insertNewSecondNode (String airport)
  {
    if (length == 0) return;

This operation is not defined on an empty list, so this requirement
is a precondition.

(Even better style to _do_ something when you discover an error).

Possibilities:

1) print an error message and quit
2) return a special value to caller and let them figure out what to do
3) throw and exception -- exception might get caught anywhere in the
   call stack -- conveys more information than single return value


What about preconditions for print?

1) don't have to check the non-nullness of the implicit argument
   this, because if it were null the invokation would have failed

  public static void main (String[] args) {
    List list = null;
    list.print ();      // this will cause a null reference exception

2) don't really have to check the length field, but we could, almost
   free -- suggests a form of self-repairing data structure (good idea?)

3) can we check for loops?  Could keep track of all nodes seen so far.
   Or re-traverse the list after each new element.

   (what kind of equality should we check for?)
   (how long would it take to traverse a list this way?)