cs230 Lecture Notes
Week 5 Monday

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

Standard idiom for traversing a list:

    public static void printList (Node list) {
        Node node = list;

        while (node != null) {
            System.out.print (node);
            node = node.next;
        }
        System.out.println ();
    }

Draw the state diagram.

Notice the abundance of aliasing.

Often makes life tough---handle it by using idioms.


Recursion
---------

Natural way to work with lists

1) empty list is a base case

2) recursive step is: deal with head, invoke on tail

3) proof of convergence?

Example: print backward.


    public static void printBackward (Node list) {
        if (list == null) return;

        Node head = list;
        Node tail = list.next;

        printBackward (tail);
        System.out.print (head);
    }

What's the difference between head and list?

FUNDAMENTAL AMBIGUITY THEOREM

1) sometimes a reference to a node means "this node"

2) sometimes it means "this node and all that follow" 

This ambiguity is powerful, but it can make code hard to
read.

I sometimes use two different variables that have the
same value but that play different roles.


Infinite lists
--------------

What happens if we traverse list with a loop?


Object methods for nodes
------------------------

	Node node = null;
	printList (node);       // legal
	node.printList ();      // NullPointerException

often we want to use null to represent the empty list,
and use it as the base case for recursion.

That makes object methods awkward.


Modifying lists
---------------

You can pass a list as a parameter, and the method that gets
it can modify it, up to a point.

For example:

    public static Node removeSecond (Node list) {
        Node first = list;
        Node second = list.next;

        // make the first node refer to the third
        first.next = second.next;

        // separate the second node from the rest of the list
        second.next = null;
        return second;
    }

But what about removeFirstNode?

Suggestions?


The sentinel
------------

public class List {
    int length;
    Node head;

    public List () {
        length = 0;
        head = null;
    }
}


Capital-L List is a type.  It contains two instance
variables, an integer and a reference to a node.

Little-L list is a set of linked nodes.

A List contains a reference to a list.

The List class provides

1) a handle that makes it easier to modify lists

   e.g. removeFirstNode

2) a veneer to hide ugly interfaces


IN LIST

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

        if (head != null) {
            Node tail = head.next;
            Node.printBackward (tail);
            System.out.print (head);
        }
        System.out.println (")");
    }	


IN NODE

    public static void printBackward (Node list) {
        if (list == null) return;

        Node head = list;
        Node tail = list.next;

        printBackward (tail);
        System.out.print (head);
    }    


Client view:  nice object-oriented interface, standard format output

Internal view: 

	 wrapper handles cleanup

	 helper does the work (ugly recursive class method)