University of Toronto
Department of Computer Science

CSC324 - Principles of Programming Languages

Spring 1998                                             John Mylopoulos

Programming in Java: Tutorial Notes 7

Prepared by Diane Horton



Re-implementing ListOfInts
-------------------------

 - Revise the private instance variables in class ListOfInts.

 - Develop the code for each method.  (See below for a solution.)
 
 - Trace the code for each one.

 - Use this as an opportunity to reinforce how references work,
   and to emphasize the value of careful tracing.

 - Also point out that nothing outside ListOfInts is affected by
   this entirely new implementation!



Another method	     
-----------------------

 - write a method for printing out the contents of a ListOfInts.


Solution code
-------------

class Node {
   public int data;
   public Node nextOne;

   // Constructor
   public Node (int initialValue) {
       data = initialValue;
       nextOne = null;
   }
}

class ListOfInts {

   private Node theList;
   private int numElements;
   // Don't need a maxListSize; no limit other than memory limits.

   // Constructor
   public ListOfInts() {
   // Actually, the default constructor would do the same inits for us.
        theList = null;
        numElements = 0;
   }

   public void addInt (int n) {
   Node temp = new Node(n);
        temp.nextOne = theList;
        theList = temp;
        numElements++;
   }

   public float average () {
   Node temp = theList;
        int sum = 0;
	while (temp != null) { 
                sum += temp.data;
		    temp = temp.nextOne;
		    }
        return sum / numElements;
   }

   // No different.  But how would it look if we didn't keep a counter?
   // (DO we *need* to?  If not, should we choose to?)
   public int size() {
   return numElements;
   }

   // Always returns false, but not silly to include this.  It's here
   // for backwards compatibility with the earlier version.
   public boolean full() {
   return false;
   }
}


class Student {

   private int studentNum;
   private String name;
   private ListOfInts markList;

   public Student (int n, String s) {
   studentNum = n;
   name = s;
   markList = new ListOfInts();
   }

   public void passCourse (int mark) {
   markList.addInt(mark);
   }

   public float average() {
   return markList.average();
   }

}


class Example {

   public static void main (String[] args) {

	  Student Fred, Betty;
	  Fred = new Student(12345, "Fred Flintstone");
	  Fred.passCourse(75);
	  Fred.passCourse(68);

	  Betty = new Student(90210, "Betty Rubble");
	  Betty.passCourse(92);

	  System.out.println("Fred's avg: " + Fred.average() + " and " +
                           "Betty's avg: " + Betty.average());
   }
}



Deleting the 1st element of a linked list
-----------------------------------------


   public void removeFirst () {
        theList = theList.nextOne;
        // No "free" required (or even expressible in Java).
        // If nothing refers to the old front node, it gets garbage collected.
   }


Printing a linked list in reverse
---------------------------------

- Print an existing linked list in reverse order,
  without using recursion or more than a const amount of extra memory.

   public void printReverse () {

        Node last = null;
        Node current;

	// print the one before last, and then move last back one node.
	// Continue until last gets to the front.
        while (last != theList) {
                current = theList;
                while (current.nextOne != last)
                        current = current.nextOne;
                System.out.println(current.data);
                last = current;
        }
   }



A complete program
------------------


class Node {
   public int data;
   public Node nextOne;

   // Constructor
   public Node (int initialValue) {
       data = initialValue;
       nextOne = null;
   }
}

class ListOfInts {

   private Node theList;
   private int numElements;
   // Don't need a maxListSize; no limit other than memory limits.

   // Constructor
   public ListOfInts() {
   // Actually, the default constructor would do the same inits for us.
        theList = null;
        numElements = 0;
   }

   public void removeFirst () {
   theList = theList.nextOne;
   // No "free" required (or even expressible in Java).
   // If nothing refers to the old front node, it gets garbage collected.
   }

   public void printReverse () {

   Node last = null;
   Node current;

   while (last != theList) {
	 current = theList;
		 while (current.nextOne != last)
					current = current.nextOne;
						System.out.println(current.data);
							last = current;
							}
   }

   public void addInt (int n) {
   Node temp = new Node(n);
        temp.nextOne = theList;
        theList = temp;
        numElements++;
   }

   public float average () {
   Node temp = theList;
        int sum = 0;
	while (temp != null) { 
                sum += temp.data;
		    temp = temp.nextOne;
		    }
        return sum / numElements;
   }

   public int size() {
   return numElements;
   }

   public boolean full() {
   return false;
   }
}


class Example {

   public static void main (String[] args) {

   ListOfInts l = new ListOfInts ();
   l.addInt(5);
   l.addInt(22);
   l.addInt(16);
   l.addInt(-55);
   l.addInt(9);

   l.printReverse();
   l.removeFirst();
   l.printReverse();
   }
}