Extending the List Class

Site Index

Purpose

This laboratory is intended to reinforce students’ abilities to design and analyze recursive list algorithms, and to give students hands-on experience defining subclasses of the List class described in Algorithms and Data Structures: The Science of Computing.

Prerequisites

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

Background

This exercise requires creating a subclass of 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 and Its Subclasses

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

    import geneseo.cs.sc.List;

Subclasses of List are subtle in several ways. Section 11.5.1 of Algorithms and Data Structures: The Science of Computing discusses the subtleties. For this exercise, pay particular attention to how to write makeNewList methods, and to the use of casts with the getRest message.

The Comparable Interface

One of the steps in this lab requires finding out whether one element of 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:

• a.compareTo(b) is negative if a < b
• a.compareTo(b) is zero if a = b
• a.compareTo(b) is positive if a > b

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:

    String string1 = ....;
    String string2 = ....;
    if ( string1.compareTo(string2) < 0 ) ....

It is legal to cast objects to interfaces that they implement, just as it is legal to cast to classes of which an object is an instance. 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:

    if ( ((Comparable)someList.getFirst()).compareTo( someItem ) > 0 ) ....

Exercise

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

• Develop an algorithm for the method
• Prove the algorithm correct
• Derive the worst-case asymptotic execution time of the algorithm, as a function of list size

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.

Extract Every Second Element

Design a parameterless method, everyOther, that returns a list containing the first, third, fifth, and in general every second element of a list that receives an everyOther message.

For example, sending an everyOther message to a list that contains the strings “aardvark,” “bonobo,” “capybara,” “dogfish,” and “elephant,” in that order, would return a list that contained just the strings “aardvark,” “capybara,” and “elephant.”

Note that everyOther creates and returns a new list, it does not modify the list receiving the everyOther message.

Are Two Lists the Same?

Design a method, equalLists, that takes a list as its parameter and determines whether that list contains the same elements, in the same order, as the list that receives the equalLists message. The equalLists message returns a boolean result, true if the lists are the same, and false if not.

For example, if list A contains the strings “accordion,” “banjo,” and “clarinet,” and list B also contains the strings “accordion,” “banjo,” and “clarinet,” then the expression A.equalLists(B) should yield true. However, A.equalLists(C), where list C contains the strings “accordion,” “bongo,” and “clarinet,” should return false.

Use Java’s equals message (not “==”) to determine whether elements from the lists are the same.

Final Details

Finding the List Class

File List.java can be Downloaded from the World Wide Web.

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

Turn in your solution to this exercise as directed by your instructor.

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 8, 2005 by Doug Baldwin

Site Index