cs231 Lecture Notes
Week 4, Monday

Homework hints
--------------

Here are solutions to the first two problems on the homework.
I want to use them to clarify something I didn't explain very
well last week.

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

  public void deleteFirst ()
  {
    if (length == 0) return;
    firstNode = firstNode.link;
    length--;
  }

As I said then, there is an ambiguity about references: sometime
we mean the reference itself, and sometimes the object the
reference refers to.

After looking at the programs, I realized that there is an
additional element to this ambiguity, which is WHERE the expression
occurs.

When a variable is used on the left-hand side of an assignment
statement, it is used to identify the LOCATION of the result.

When a variable appears on the right side of an assignment
(or as a method argument), it yields its CONTENTS.

For example, in insertNewFirstNode, the crucial line is:

    firstNode = newNode;

That means take the CONTENTS of newNode and put it at the LOCATION
named firstNode.

Similarly,

    firstNode = firstNode.link;

means "get the CONTENTS of the link field from the object referred
to by firstNode and put it in the LOCATION named firstNode."

The following table might help organize some of these thoughts:

Left side	    Right side
Variable	    Value
Location	    Contents
Reference	    Object

Another kind of invariant
-------------------------

Notice that every time you add a node to a list, you have to
increment length.

Every time you remove a node from a list, you have to decrement
length.

That's because in order for a list to be well-formed, it must
be true that the length is equal to the number of nodes in
the list.

This property is an example of an "object invariant".

Something that must be true in order for an object to be well-formed.

(The other kind of invariant might be called a path invariant,
because it is something that must be true at a given point in
a program, regardless of the path we took to get there).

When we modify a data structure, we sometimes violate the invariant
briefly.

Usually the requirement is that the invariant must be restored
by the end of every modifier.

If we know

1) all the constructors create objects with the invariant

and

2) all the modifiers maintain the invariant,

then it is easy to "prove" that the invariant is always true
(at least outside the modifiers).

In order to perform a proof like this, we need to be able to
identify all the modifiers.

Object invariants are good things to put in comments.

It is a good idea to identify modifiers in comments.

Exercise: write a method called checkList that returns true
if the current LinkedList is well-formed and false otherwise.

What are the invariants for a list?

Can we check all of them without danger of causing an exception?

Can we check all of them and guarantee termination?


More homework hints
-------------------

For reverse, I wrote a recursive method named
ListNode.reverseNodes that takes a ListNode as an argument
and that returns a ListNode.

So, in LinkedList I have...

  // reverse: rearranges the nodes in the list, reversing their
  // order (modifier)
  public void reverse () {
    firstNode = ListNode.reverseNodes (firstNode);
  }
  
And in ListNode I have the method that does the real work.

This pattern is common; it is sometimes called a wrapper-worker
pattern.  In this case, reverse is just a wrapper (a short method
that does little other than invoking another method).

reverseNodes is called the worker because it does the actual
work.

The usual reason for a wrapper-worker pattern is to provide
a pretty interface (like reverse) for an ugly function.

I did the same thing with copy (the worker is called ListNode.copyNodes).

Draw a picture of insertNode.

Subtle interface design issue: should LinkedList operations take
airports as Strings or nodes?  In other words, does the client
allocated the ListNode objects or do we do that inside LinkedList?