Laboratory Exercise

Lab 8 — Extending the List Class

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004

Purpose

Prerequisites

Understanding of sections 11.1 through 11.5.1 of Algorithms and Data Structures: The Science of Computing.

Background

This exercise requires using the List class that accompanies Algorithms and Data Structures: The Science of Computing. The exercise also requires comparing elements of lists to see if one is less than another, something that is easiest to do if the elements all implement a Java interface named Comparable.

The List Class

Chapter 11 of Algorithms and Data Structures: The Science of Computing thoroughly describes the List class. A complete implementation of this class is available, in a file named List.java. The “Final Details” section of this document explains where to find this file.

Any Java source file that uses the List class should “import” it via a statement of the form

The Comparable Interface

One of the steps in this lab requires finding out whether one element in a list is less than or equal to another. The standard Java class library defines an interface named Comparable that is implemented by all standard classes for which one value can meaningfully be less than another. (See section A.5.3 in the appendix to Algorithms and Data Structures: The Science of Computing for an introduction to interfaces.) Any class that implements Comparable handles a compareTo message, which takes an arbitrary object as its only parameter, and returns an integer according to the following rules:

Thus, for example, the following code compares two strings (the String class implements Comparable, using alphabetical order to decide whether one string is less than another) to see if string1 is less than string2:

It is legal to cast objects to interfaces that they implement, just as it is legal to cast to classes that an object is an instance of. For example, here is a fragment of code that asks whether the first item in a list of Comparable objects (someList) is greater than object someItem:

Exercise

Design and analyze a subclass of List that includes the methods described below. Specifically, do the following for each method:

Finally, write in Java a subclass of List that includes all of the methods. Write a main program that tests this subclass (lists of strings are good things to test the subclass with, since strings are objects that can be compared for equality and for one string being less than another).

Is a List in Order?

Design a method to determine whether the elements of a list are in increasing order. This method should have no parameters, and should return a boolean value: true if the list contains one or zero elements, or if each element in the list is less than or equal to the element after it; false in all other cases. Assume that all elements in the list are comparable to each other, i.e., that it is meaningful to ask whether one element is less than another (in Java terms, assume that all elements implement the Comparable interface, described above).

Does a List Contain Duplicates?

Design a method to determine whether any two elements of an unordered list are equal to each other. This method takes no parameters, and returns a boolean value: true if there are two (or more) equal elements in the list, and false otherwise.

Extract the n^th Element

Design a method that takes an integer, n, as its only parameter, and that returns the n^th element of a list. Number elements starting at 1, i.e., the head of the list is element 1, the head of the tail is element 2, and so forth. If n is less than 1, or greater than the total number of elements in the list, the method should return null (null is a special constant in Java that denotes the absence of an object).

For example, if the method is named nth and someList is a list containing the strings “apple,” “banana,” and “canteloupe,” in that order, then someList.nth( 2 ) should return “banana,” while someList.nth( 4 ) should return null.

Final Details

Finding the List Class

Documentation for the List class is also available on the Web. The main documentation page is an index to documentation for all the Java classes written for use with Algorithms and Data Structures: The Science of Computing. To see the documentation for a specific class, click on that class’s name in the left-hand panel of the page.

Submitting Your Work

This lab is due on Monday, November 8. Turn in a printout of the code you write, and the correctness proofs and execution time derivations for each method. The proofs and derivations may be comments in your code, or they may be on a separate sheet of paper.

In addition to your code, proofs, and derivations, turn in a short paragraph describing one or two things you encountered while designing and analyzing the algorithms in this lab that are different from things you have encountered in previous algorithm designs or analyses, and one or two that are similar. This paragraph may also be comments in your code, or on a separate sheet of paper, whichever you prefer.