cs231 Lecture Notes
Week 4, Friday

Quiz solution (from Wednesday):

I have not run or tested the following code.  Can we prove it
correct?

  public boolean check () {
      int count = 0;

      for (ListNode node = firstNode; node != null; node = node.link) {
	  count++;
	  if (count > length) return false;
      }
      if (count < length) return false;
      else return true;
  }


Doubly-linked list: discussed in class Wednesday.  See
handout with Doubly-Linked List code.


Homework solutions:

Key ideas on this homework:

1) build-generally useful methods like insertNewFirstNode and
insertNewLastNode and then use them to build more complicated
things.

Example:  copyIterative and copyReverse are nearly identical

  // copyIterative: same as copy, different algorithm
  public LinkedList copyIterative () {
    LinkedList newList = new LinkedList ();
    for (ListNode node = firstNode; node != null; node = node.link) {
      newList.insertNewLastNode (node.airport);
    }
    return newList;
  }
  
  // copyReverse: same as copyIterative, except the list comes out
  // backwards (this method is functional; i.e. not a modifier)
  public LinkedList copyReverse () {
    LinkedList newList = new LinkedList ();
    for (ListNode node = firstNode; node != null; node = node.link) {
      newList.insertNewFirstNode (node.airport);
    }
    return newList;
  }
  
Notice that we are not doing any pointer-manipulation in these
methods!  Easy to prove correctness.  Easy to write one once
we have tested the other.

2) use wrapper methods that transform interfaces from one
structure to another.

Example: reverseIterative uses copyReverse, which is a function,
	 to implement reverse, which is a modifier

  // reverseIterative: same as reverse, different algorithm (modifier)
  public void reverseIterative () {
    LinkedList newList = copyReverse ();
    firstNode = newList.firstNode;
  }


Performance danger!
------------------

Abstraction is a beautiful thing, but it can hide performance
behavior in dangerous ways.

For example, looking at copyIterative and copyReverse, it is
not immediately obvious that one is an O(n) algorithm and the
other is an O(n^2) algorithm.  Which is which?

Recursion with objects
----------------------

We have done a few kinds of recursion, gradually building up

1) recursive flow of execution (countdown)
2) recursive computation (factorial)
3) recursion with Objects as parameters (mergeSort)
4) recursion with Objects as return values (reverse)

The wrappers:

  // copy: return a new LinkedList, with new ListNodes that contain
  // the same info as the current list
  public LinkedList copy () {
    LinkedList newList = new LinkedList ();
    newList.firstNode = ListNode.copyNodes (firstNode);
    newList.length = length;
    return newList;
  }
  
  // reverse: rearranges the nodes in the list, reversing their
  // order (modifier)
  public void reverse () {
    firstNode = ListNode.reverseNodes (firstNode);
  }

The workers:

  public static ListNode reverseNodes (ListNode head) {
    if (head == null) return null;
    ListNode tail = reverseNodes (head.link);
    return addLast (tail, head);
  }

  public static ListNode copyNodes (ListNode head) {
    if (head == null) return null;
    ListNode newTail = copyNodes (head.link);
    ListNode newHead = new ListNode (head.airport, newTail);
    return newHead;
  }

If you still can't get yourself to accept the leap of faith,
you can draw a stack diagram for these methods, but you really
should start to wean yourself from doing it.

Again, the performance issue raises a complication here.
Remember that addLast is an O(n) operation, so reverseNodes
is O(n^2)!