Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)
The List library class is a complete Java implementation of the list class described
in chapter 11 of Algorithms and Data Structures: The Science of Computing. Source
code for the class is available in Java, so that students can use it
as a starting point for exercises related to the chapter.
The List class provides a set of primitives in terms of which
students (and instructors) can write Java code for list algorithms, thus gaining
hands-on experience with designing, coding, and using such algorithms. Students
will typically be assigned to develop these algorithms
in laboratory or homework exercises, although the algorithms could also be
shown as demonstrations in lectures.
The easiest way to code new list algorithms, and the way most consistent
with object oriented principles, is to make them methods of some subclass of
List. Most exercises involving the List class will
thus ask students to define such a subclass. However, simple algorithms can
be coded within a main method. This is a particularly valuable
thing to do in exercises that introduce students to lists, since it lets students
concentrate on understanding the basic operations on lists before dealing with
the subtleties
of defining List subclasses.
The List class as implemented follows very closely the class
described in Algorithms and Data Structures: The Science of Computing.
Most of the code
comes directly from section 11.5.2. Thus most of the class’s design
is described in the text. However, the implemented class does have some features
not in the text’s version, including:
List( Object ), which initializes
a list to contain a single object. This constructor is a convenience
for
clients who want to create short but non-empty lists.setFirstItem method has been added, that allows code in subclasses
to alter a list’s head.concat method is public, and works correctly even when
the recipient of the concat message is empty.printListForward method from section 11.5.1 has been provided
as a primitive method of List.copy method has been added, which creates a new list that is a copy of
the list receiving the copy message.save and restore have been added, which
write a list to a file, and read a list from a file, respectively. Both methods
take the name of
the file as a parameter. These methods allow instructors to provide
test data to students in the form of pre-built lists, and allow programs
that manipulate large lists to save those lists between runs rather than
having
to reconstruct them every time the program starts.toString method has been provided, so that lists can convert
themselves to meaningful strings, as most other Java objects do.Note that some of the features in the implemented List class
solve exercises in the text. The affected exercises are…
concat that work for empty
lists)Instructors who assign text exercises may wish to take this into consideration.
This List class has no connection to the List interface
in Java’s
standard class library — our class reflects a different view of lists,
one that is explicitly designed for pedagogical purposes, particularly to highlight
lists as recursive structures.
A file named List.java,
which defines the List class, can
be downloaded from the Web. Documentation for the class
is also available on the Web.
List.java needs to be present in any program that uses lists.
The List class is part of the geneseo.cs.sc package.
Source files that use the class thus usually import it.
Copyright © 2004 Charles River Media. All rights reserved.
Revised Aug. 9, 2005 by Doug Baldwin