cs231 Lecture Notes
Week 3, Friday

The key to working with linked data structures is to understand
the basic operations at the level of mechanism, and then construct
a framework that allows you to write and interpret programs abstractly.

For example, we are going to look at two fundamental methods
for traversing linked lists (forward and backward).

In each case, we will interpret the program mechanically, once.
From then on we can forget the details and think of the methods
abstractly.

Traversal
---------

How do you traverse a List?

  public void traverse () {

    ListNode node = firstNode;

    while (node != null) {

      System.out.print (node.airport);
      node = node.link;

    }
  }    

OR, often

    for (ListNode node = firstNode; node != null; node = node.link) {

    }

OR, we could use the length field to control how many nodes to
look at.

This idiom is as common as traversing an array (and should
be as foolproof).

An idiom is a kind of abstraction.  From now on, you don't
have to think through the details, you can use the idiom.

So, for example...

  public void print () {
    System.out.print ("(");

    // start at the beginning of the list
    ListNode node = firstNode;

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


What can go wrong in a list traversal?

1) null references?  Nope.

2) a loop in the list!

Sometimes lists with loops in them are useful, but usually
we define a well-structured list as one without loops.


Traversing a list backward
--------------------------

There is also a standard idiom for traversing an array backward,
using recursion.  Here is what it looks like.

In LinkedList:

  public void printBackward () {
    System.out.print ("(");
    ListNode.printBackward (firstNode);
    System.out.println (")");
  }    

In ListNode:

  public static void printBackward (ListNode node) {
    if (node == null) return;
    printBackward (node.link);
    System.out.print (node.airport + ", ");
  }    

Why is ListNode.printBackward a class method?

1) Because the easiest base case to deal with is a null list.

2) You can't invoke a method on a null object (although I
   think you should be able to).

3) But you _can_ pass a null object as an argument.


Draw a stack diagram for these methods.  Not easy, but...

Now interpret abstractly.  Actually, there are two abstractions:

1) the leap of faith.  Don't follow the stack; assume the
   recursive call works.

2) when you pass a ListNode as an argument, you are also passing
   the rest of the list (abstractly)