CIS 121 April 10, 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.
Recall that we have discussed stacks and queues which you will be using in your assignment. Remember that you will need to implement the queue methods yourself but should use the predefined Stack class.

Linked Lists

On Friday we began talking about linked lists. This is a very important data structure so lets look again at the example. A linked list is a list of nodes each of which contains a reference to another node in the list.

Recall that we defined a class called Node as follows. This is found in your textbook on page 507. 

class Node {
   private Object datum;
   private Node link;

   public Node(Object item,Node pointer) {
      datum = item;
      link = pointer;
   }
}
Note the important thing about this class definition is that it contains an instance variable which is of the same type as the class we are defining! For this reason it is called a self-referential structure.

In languages such as C++ there is the notion of a pointer. A pointer is a special type of variable that contains the address of the location in memory of some other variable such as an integer. This is how linked lists are implemented in those languages. In Java we do not have a pointer variable type. But we can use a self-referential structure to give us the same functionality without the inherent problems that come will directly accessing memory locations. For example, what if we make a mistake and accidentally point to the area of memory where the operating system is and write over it. Java allows us to avoid these problems. However, we can still think of a reference to a Node as a pointer. If we have the statement head = new Node("text",null);, then we can imagine a variable called head which is of type Node as pointing to the new Node object we have created. So in this discussion whenever we assign a Node variable to a Node object we will say that that Node variable is pointing to the Node object.

Notice the parameters to the constructor. It accepts an Object and a parameter of type Node. The instance variable link is set to the Node object sent in.

Now suppose we have the following statement in an application.

Node head = null;

The reason we do this is to establish the head of our list. This is necessary because we must have some way to access the beginning of our list.

We can imagine in memory the following.


We have an Object of type node which is set to null.

Now we add the following statement.

head = new Node("Fred",head);

Recall that the first thing that is executed is the code on the right of the equals. We create a new instance of a Node object sending it the String "Fred" and the Node variable head which we already created. So the new Node object will have the string "Fred" as its datum variable, and null as its link variable. After the new Object is created, we then readjust head to point to this new Object.


Notice that since null is the link variable in the Node object containing the string Fred, this Object is at the end of the list.

Now let us add the following statement.

head = new Node("Esther",head);

Recall again that the first thing executed is the right side of the equals. We create a new instance of a Node object sending it the string "Esther" and the previous value of head. So now the link variable in the Node object containing Esther is the Node object containing Fred. Again we can think of this as a pointer, and we will illustrate it by showing the link variable in the Node object containing Esther pointing to the Node object containing Fred.

After this new Object is created we adjust head so that it now points to the Node object containing Esther instead of the Node object containing Fred.


Now we add the final statement.

head = new Node("Lamont",head);

Following the same reasoning as above, we create a new Node object containing Lamont and set its link variable to the Node object containing Esther. We illustrate it by saying that the link varible in the Node object containing Lamont points to the Node object containing Esther.

After the new Object is created we then adjust head to point to the Node object containing Lamont.


So now we have a linked list. The beginning of the list is pointed to by head and the end of the list is indicated by the Node containing null as its link variable.

Now that we have the list created, suppose we want to traverse the list and print out the String variable in each list. 

for (Node start = head;start != null;start = start.link)
   System.out.println(start.datum);
Notice what is happening in this code. We normally use a for loop when dealing with integers but it is perfectly valid to use it with other data types. The first part of the for loop is the initialization, the second part is the stopping criterion, and the third part is the code that is executed each time after the body of the for loop is executed.

So we create a new Node variable called start and initialize it to head. As long as start is not null we print out the String in the node pointed to by start and then adjust start to point to the next node in the list. The traversal stops when start becomes null, i.e. after we get to the last node in the list and start is set to its link variable.

Now let's put these code pieces together in a program. 

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();
   }
   
}
The output of this program is 
Lamont
Esther
Fred
You may download this source code if you want to experiment with it.

On page 511 of your textbook the authors present a LinkedList class and implement its methods. Let us look at the interface of this class. 

public LinkedList {
   public LinkedList();

   public void insert(Object datum);
   public boolean delete(Object scrap);
   public void displayList();
   public boolean isEmpty();
   public int node();
}
Three of the instance variables in the class are 
Node head;
Node temporary;
Node tail;
There is also another instance variable. 
int nodeCount;
Let us now consider the code that is given for inserting and deleting. 
public void insert(Object datum) {
   if (head == null) {
      head = new Node(datum,head);
      tail = head;
   } else {
      temporary = new Node(datum,temporary);
      tail.link = temporary;
      temporary = null;
   }
}

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;
}