Lists in Java

Goals

This lab applies ideas of box-and-pointer representations and provides practice implementing lists in Java.

Background: Lists in Scheme

The reading for this lab describes box-and-pointer diagrams as a graphical model for lists.

1. Draw box-and-pointer diagrams for each of the following lists:

   
      ((x) y z)
      (x (y z))
      ((a) b (c ()))
   

Implementing Scheme List Operations in Java

The reading also outlines the implementation of links in Java in two steps.

1. Class ~walker/java/examples/lists/ListNode.java provides the basic node structure that corresponds to a box and pointer.
2. Program ~walker/java/examples/lists/ListLikeScheme.java outlines a list class with these methods.

   • The constructor should create a new object, and initialize first to null.

   • The car method should return the contents of the data field in the ListNode designated by first. This information is obtainable as first.getData() -- applying the getData method for that node. However, if the list contains no elements (i.e. is a null list), car might throw a NullPointerException.

   • The isNull method should test whether or not first is null.

   • For the cdr method, we must choose whether to alter the current list or return a new one. For illustration, we create and return a new list. Thus, we declare a local variable temp, initialize it with the ListLikeScheme constructor, and set its first variable to the next element after the first node. The relevant syntax is

     
     List temp = new ListLikeScheme ();
     temp.first = first.getNext();
     return temp;
     
     

   • For variety, we implement cons to alter the current list object rather than to return a new one. In this form, cons must create a new ListNode, put the data in it, update the next field and set the variable first to this new node. Since much of this work can be done with a ListNode constructor, the actual code is quite short:

     
     first = new ListNode (newData, rest.first);
     
     

   • The size method parallels the recursive list processing we enjoyed in Scheme. Using a husk-and-kernel approach, the real work is done in a kernel with keeps recursing and adding one until a null object is identified. Movement from one ListNode to the next is accomplished by utilizing the getNext method from the current node. As in Scheme, the husk just starts the process -- in this case, calling the kernel with the first node and a count of 0.

   • The length method parallels an iterative movement through the nodes, counting as it goes. Here, a separate variable ptr is used to keep track of how far processing has proceeded through the sequence of nodes. As in the recursive version, processing continues until a null object is found.

   • Finally, our ListLikeScheme class includes a toString method which formats a string of the data elements just as might be seen in Scheme. As noted in the lab on generalization, Java often utilizes a toString method and inheritance as part of printing.

Use these definitions and methods as the base for the following explorations of lists in Java.

2. Copy ~walker/java/examples/lists/ListNode.java and ~walker/java/examples/lists/ListLikeScheme.java to your account. Compile and run them to check that they work. Also, read through the code. Ask questions about any sections you do not understand.

3. Add a method second to ListLikeScheme which returns the second element in a list (if present), or which throws a NullPointerException if the list is null or has only one element. (In this and subsequent exercise, you will want to add lines to main to test your methods.)

4. Add a method count which counts how many times a specified object appears on a list. count should have one parameter -- the object to be counted.

   Note: If item is the object to be counted, you can compare item with any other element with the test item.equals(element). Here you will need to check item with the data in successive nodes.

5. Add a method last which returns the last item on the list.

6. Add a method toReverseString which returns a string representing the elements of the list -- ordered from last to first. In writing this code, you should modify the iterative method toString.

7. Add a method toReverseStringAlt which uses recursion rather than iteration to return the same result as toReverseString.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-lists-in-java.shtml

created May 4, 2000 last revised March 24, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.