CIS 121 April 12, 2000

  1. This is the second and last week of advising for Juniors, Seniors, and Graduate Students. Freshmen and Sophomores must sign up at http://www.cis.usouthal.edu/advising. Time is running short. Advising for Juniors, Seniors, and Graduate students will only last for two weeks. After that time, even if you meet with an advisor, there will still be a block placed on your registration. So make sure you sign up soon. Advising for Freshmen and Sophomores will last for three weeks. Each Freshmen and Sophomore is assigned a particular week to be advised. You will be told what week you have been assigned when you sign up.
  2. The Annual ACM Banquet will be held this year on the Battleship Alabama on April 22. The winners of the scholarships and fellowships will be announced at the banquet. The cost of the banquet is $25. The banquet will consist of a nice dinner and dancing after dinner on the Battleship. All students are encouraged to attend. If you need more information, you may contact the ACM Faculty sponsor, Dr. David Langan.
Before we continue talking about linked lists we will look at an example of a problem that has occured in several programs. Consider the following code. 
import java.awt.*;
import java.awt.event.*;

public class Example extends Frame implements ItemListener {
   Checkbox checkbox1 = new Checkbox("One");
   Checkbox checkbox2 = new Checkbox("Two");
   TextField myTextField;

   public Example() {
      setBackground(Color.white);

      setLayout(new FlowLayout());

      add(checkbox1);
      add(checkbox2);

      checkbox1.addItemListener(this);
      checkbox2.addItemListener(this);

      TextField myTextField = new TextField();

      add(myTextField);
   }

   public void itemStateChanged(ItemEvent e) {
      if (e.getStateChange() == ItemEvent.SELECTED) {
         if (e.getItem() == "One")
            myTextField.setText("One");
         if (e.getItem() == "Two")
            myTextField.setText("Two");
      }
   }

   public static void main(String[] args) {
      Example myExample = new Example();
      myExample.setVisible(true);
      myExample.setSize(500,100);
   }
}
You may download the source code.

Recall again the code we used to build a linked list. This is a simple list that only has a method to traverse the list. 
public class List {
   Node head;

   public class Node {
      Object datum;
      Node link;

      public Node(Object item,Node pointer) {
         datum = item;
         link = pointer;
      }
   }

   public List() {
      head = null;

      head = new Node("Fred",head);
      head = new Node("Esther",head);
      head = new Node("Lamont",head);
   }

   public void traverse() {
      for (Node start = head;start != null;start = start.link)
         System.out.println(start.datum);
   }

   public static void main(String[] args) {
      List myList = new List();

      myList.traverse();
   }
   
}
On page 511 of the textbook they define a more useful Linked List class. 
public LinkedList {
   public LinkedList();

   public void insert(Object datum);
   public boolean delete(Object scrap);
   public void displayList();
   public boolean isEmpty();
   public int node();
}
The instance variables for this class are 
Node head;
Node temporary;
Node tail;
int nodeCount;
As we noted last time, the last three methods are very easy to implement.

displayList() can be implemented like we did in our example.

isEmpty() can be implemented in different ways. We could look to see if the head of the list is also the tail or investigate whether or not the nodeCount instance variable is 0.

node() is easily implemented by returning the value of nodeCount.

The other two methods are more complicated to implement. Let us look again at how the book implemented them.

When a Linked List object is created, the three Node instance variables, head, temporary, and tail are all set to null, and nodeCount is set to 0.

public void insert(Object datum) 

public void insert(Object datum) {
   if (head == null) {
      head = new Node(datum,head);
      tail = head;
   } else {
      temporary = new Node(datum,temporary);
      tail.link = temporary;
      tail = temporary;
      temporary = null;
   }
}
When we insert a node into the list we check two cases.

Case I

The list is empty.

In this case we create a new Node object and have the head and tail point to that object since it is the only one in the list. 
   if (head == null) {
      head = new Node(datum,head);
      tail = head;
   }


Case II

The list is not empty.

In this case we create a new Node object and assign the instance variable temporary to it. We readjust the link variable of the tail of the list (which is null since it is at the end of the list) to point to this new Node object which now becomes the tail of the list since the original value of temporary is null. Then temporary is reset to null. 

   } else {
      temporary = new Node(datum,temporary);
      tail.link = temporary;
      tail = temporary;
      temporary = null;
   }
Notice that in this implementation of the linked list each new node goes at the end of the list. This behavior resembles that of a queue whereas our example where we inserted new nodes at the head of a list resembled a stack.

public boolean delete(Object scrap) 

public boolean delete(Object scrap) {
   Node previous = head;

   for (Node current = head;current != null;current = current.link) {
      if (current.datum.equals(scrap) && previous == current) {
         head = current.link;
         if (head == null)
             tail = null;
         nodeCount--;
         return true;
      } else if (current.datum.equals(scrap) && current.link != null)) {
         previous.link = current.link;
         nodeCount--;
         return true;
      } else if (current.datum.equals(scrap) && (current.link == null)) {
         tail = previous;
         previous.link = null;
         nodeCount--;
         return(true);
      }
      previous = current;
   }
   return false;
}


When we delete a node from the list, we check three cases. We check these cases inside a for loop. Notice how this method works. We create a local Node variable called previous, and initialize it to point to the head of the list. We then examine each node in the list. The Node variable previous will give us a pointer to the last node we examined, and the Node variable current will give us a pointer to the current node we are examining. Notice that this method returns a boolean value because unlike the insert method where the only problem is we can run out of memory, we could try to delete a node that isn't in the list. So if we find the node and delete it we will return true, otherwise we will return false.

Case I

The node to be deleted is the first node in the list.

In this case the value of previous will equal the value of current. So we adjust the Node variable head to point to the second node in the list. If there is no second node, then head become null. So we also set tail to be null (since if there is only one node in the list both the head and tail Node variables point there). We then reduce the nodeCount and return true. 

      if (current.datum.equals(scrap) && previous == current) {
         head = current.link;
         if (head == null)
             tail = null;
         nodeCount--;
         return true;
      }


Case II

The node to be deleted is between the first and last node in the list. In this case we readjust the link variable in the node pointed to by previous to be equal to the link variable pointed to by current. This effectively removes the node pointed to by current from the list. We then reduce nodeCount and return true. 

      } else if (current.datum.equals(scrap) && current.link != null)) {
         previous.link = current.link;
         nodeCount--;
         return true;
      }


Case III

The node to be deleted is the last node in the list.

In this case previous point to the node which will become the last in the list. So we readjust tail to point to it. Then we must set the link variable in this node to null since that is our criterion for the end of the list. We then reduce nodeCount and return true. 

      } else if (current.datum.equals(scrap) && (current.link == null)) {
         tail = previous;
         previous.link = null;
         nodeCount--;
         return(true);
      }


After all three of these cases are checked, we reset the previous node to point to the current node.

If we haven't returned true by the time the for loop is finished, then we haven't found the node so we return false.

Notice that after a node is deleted from the list we don't have a way to reference it so by definition it is garbage. Each Java program spins a garbage collection thread, and this is how Java effects garbage collection.

Notice that in our traversal of the list from earlier we used a simple while loop that stopped when we hit the end of the list. There is another way of traversing the list. Consider the following code. 
   public void traverse(Node next) {
      if (next != null) {
         System.out.println(next.datum);
         traverse(next.link);
      }
   }
We overload the method traverse by adding a new instance of this method with a different parameter list. The parameter it accepts is a Node variable. Notice the important this in this code is that instead of simply printing out a value and then going to the next node, the method actually calls itself!

This is a very simple example of a very powerful feature of a programming language called recursion.

The most important feature of a recursive method is that we must provide a way for the method to stop calling itself. That is the method must at some point return an actual value and not just call itself again.

This is accomplished in this method by checking to see whether or not the Node variable sent to the method is null. This happens when we send the link variable of the last node in the list to the method.

Today we want to study two very simple mathematical examples of recursion, factorials and the Fibonacci number.

Factorials

Recall that n! = n * n-1 * n-2 * ... * 1.

The Fibonacci numbers

The Fibonacci numbers are a sequence of number, Fn, such that 

F1 = 1,
F2 = 2,
and if n > 2,
Fn = Fn-1 + Fn-2

Let's examine how we can produce factorials and Fibonacci numbers with ordinary means, and then how we can produce them using recursion.