CS 214 Lab 11: Java Introduction

Begin by creating a new java directory within your new 11/ subdirectory. Then copy the file Max.java from the course labs/11/java directory into your java directory. Use your favorite text editor to open this file, customize its opening documentation, and take a moment to study it.

Lists in Java

The earliest versions of Java did not provide a built in type for a list. However, since version 1.2, the Java Collections Framework has provided a common set of interfaces for Lists, Sets, Maps, etc. A LinkedList is thus available in standard Java by importing java.util.LinkedList. Since it is a standard part of the language, we will use it today.

Defining a `list`

Begin by adding an import statement to Max.java that imports java.util.LinkedList. Given the import statement, a LinkedList object can be defined as follows:

   ListDef        ::=   LinkedList< Type > idList
   IdList         ::=   identifier MoreIds
   MoreIds        ::=   Ø | , identifier MoreIds

where Type is the type of value to be stored in the list. The Type used must be a class/reference type though. As you may remember, Java is mostly object-oriented, but includes several "primitive" types in addition to the reference types. We are interested in a list of integers, but int is a primitive type, not a reference type. To get around this limitation, Java provides "wrapper" classes for each of the primitive types (these include Integer, Double, Character, Boolean, Long, Byte, and Short). Using this information, we might thus define within Max.java several LinkedList objects capable of storing Integer values by writing

   LinkedList<Integer> list1 = null, 
                       list2 = null, 
                       list3 = null;

These declarations tell the compiler that list1, list2, and list3 are handles for LinkedList objects, but they do not yet allocate storage for the lists. To allocate storage (on the heap) we must use new operation to ask the memory management system to get us a piece of memory big enough to store a list. We can do declaration and allocation for a handle in one line as follows: :

   LinkedList<Integer> list1 = new LinkedList<Integer>();

Add appropriate statements to Max.java to declare and allocate storage for list1, list2, and list3. Save your work, build the program, and then continue when this much is free of syntax errors.

Printing a `List`

Given that a LinkedList is defined in the Java Collections Framework, you may be hoping that the framework provides us with the ability to print a LinkedList, and you'd be right! However, the standard System.out.print() mechanism prints a LinkedList with square brackets and commas separating the items. In order to learn a bit more today, we're going to print a LinkedList without square brackets and commas.

Considering the specification for our print operation, we might build the following stub:

   public static void print(LinkedList<Integer> aList)
   {
   }

To print the items in a list, we need to traverse the list. For any Java collection class (such as LinkedList), an object can be traversed using an iterator, which is an abstraction of a pointer. Standard Java provides an Iterator type for its various collections in Java.util.Iterator, so take a moment to add a statement to import this. Given that import, an iterator for a LinkedList of Integers can be created using the LinkedList class's iterator() method:

   Iterator<Integer> listIterator = aList.iterator();

The iterator() method returns an Iterator object that we can use to traverse the list sequentially.

(FYI: The LinkedList class is a doubly-linked list, so it also provides a listIterator(index) method that returns a bi-directional ListIterator for situations in which we need to traverse a list in both forward and reverse directions, but that is more functionality than we need for today.)

The Iterator class provides multiple methods that allow us to work with the list, including:

next(): Returns the next element in the iteration and updates the cursor position
hasNext(): Returns true if the iterator has more elements beyond the current cursor position

Using this information, we can define a method to print() a LinkedList of integers as follows:

    public static void print(LinkedList<Integer> aList){
	Iterator<Integer> listIterator = aList.iterator();
	while (listIterator.hasNext()){
	    System.out.print(listIterator.next() + " ");
	}
	System.out.print('\n');
    }

Add this definition to Max.java. Then uncomment the lines that call print() and verify that this much of the program works before continuing.

Finding the Maximum

In addition to providing classes for common collections, Java also provides a number of standard algorithms that solve common problems, including a max() algorithm. These are part of the Collections framework, and can be accessed by importing java.util.Collections.

With the import in place, we can use a statement like the following to find and print the maximal element in a list:

   System.out.println("Max of list1: " + Collections.max(list1));

Add the necessary statements to Max.java to display the maximum values in each of list1, list2, and list3, along with descriptive labels. Then build and run your program, and verify that it correctly finds the maximum values in each list.

That concludes the Java introduction for this lab.

Turn In: Create a script file in which you use cat to display the contents of your file, show that it compiles without error, and that it runs correctly.

Calvin > CS > 214 > Labs > 11 > Java

This page maintained by Joel Adams.