Laboratory Exercise

Lab 9 — 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 creating a subclass of the List class that accompanies Algorithms and Data Structures: The Science of Computing.

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

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.

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).

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.

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

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

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, March 28. Turn in printouts of any code you write, along with your correctness proofs and execution time derivations. The proofs and derivations can be comments in your code, or they can be on separate sheets of paper.

In addition to your code and its analyses, turn in a couple of sentences asnwering the following question: Most people find the List class harder than other classes to create subclasses of—is there something inherent in lists that makes them hard to subclass, or is the difficulty just coincidence?