CS231 lecture notes, Fall 1998
Week 2, Friday

Reading Standish Chapter 3.1 to 3.5

Help with the List assignment:

  public void deleteFirst ()
  {
    head = head.next;
    length--;
  }

Pretty trivial, but draw the pointers and arrows to convince yourself
it's correct.

insertAfter is easier than insertBefore

  public void insertAfter (ListNode node, ListNode newNode)
  {
    newNode.next = node.next;
    node.next = newNode;
    length++;
  }

But, what are the preconditions?

1) node must be in the list
2) newNode must be non-null

Once we have insertAfter, insertBefore is easier:

  public void insertBefore (ListNode node, ListNode newNode)
  {
    insertAfter (node, newNode);
    String temp = node.airport;
    node.airport = newNode.airport;
    newNode.airport = temp;
  }

As usual, in order to swap two things we need a temporary.

insertAfter is implicitly invoked on _this_

Does this swapping of data fields seem kosher?  Does it
imply another precondition?

1) There must be no other pointers to node (aliases for node).
   Can we check that?

For lists, it is probably a good idea to insist on no sharing,
for just this reason.

The book provides insertNewLastNode

  public void insertNewLastNode (String airport)
  {
    ListNode newNode = new ListNode (airport, null);

    if (head == null) {
      head = newNode;
    } else {
      ListNode node = head;
      while (node.next != null) {
	node = node.next;
      }
      node.next = newNode;
    }
    length++;
  }

With that, cloneList gets much easier:

  public List cloneList ()
  {
    List newList = new List ();

    for (ListNode node = head; node != null; node = node.next)
    {
      newList.insertNewLastNode (node.airport);
    }
    return newList;
  }

Notice the list traversal idiom in the form of a for loop.

Also, reverseList is virtually identical, except that we add the
nodes to the end instead of the beginning:

  public List reverseList ()
  {
    List newList = new List ();

    for (ListNode node = head; node != null; node = node.next)
    {
      newList.insertNewFirstNode (node.airport);
    }
    return newList;
  }

The book asks for a slightly different interface for reverse ()

  public void reverse ()
  {
    List newList = this.reverseList ();
    head = newList.head;
  }

A short method like this that provides a slightly different
interface for the same function is called a veneer.

We can implement concat using the same idiom:

  public void concat (List two)
  {
    for (ListNode node = two.head; node != null; node = node.next)
    {
      insertNewLastNode (node.airport);
    }
  }

Traverse the second list adding each element to the end of the
first list.

The result does not involve any sharing between the two lists.
Probably better than the alternative, since sharing violates
the preconditions for some other methods.

Preconditions?  What if either list is null?  Still work?