Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004
A collection (or container) class is a class whose instances contain multiple
other objects. The List class
introduced in chapter 11 of Algorithms
and Data Structures: The Science of Computing is an example of a collection.
Collections are not fundamentally different from other classes
(every object oriented programming technique used in collections can be and
is used in other situations too), but many programmers find collections
confusing at first. The idea that objects can be stored in and retrieved
from another object takes some getting used to, and collections are the first
application many people see for several powerful object oriented
programming techniques.
This exercise introduces collections, and particularly the way List acts
as a collection, by asking students to write a series of programs that use lists.
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;As explained in appendix section A.2.1 of Algorithms and Data Structures:
The Science of Computing, Java has two kinds of data: objects and non-objects
(e.g., int, char, double, etc.).
List objects (and most other collections) can hold any kind of object,
but that
seems to exclude all the non-object data that Java programmers might work
with. Fortunately, the designers of Java anticipated this problem, and provided “wrapper” classes
for all the non-object data types. A wrapper is a very simple object that basically
does nothing except contain one value of a non-object type. For example, instances
of the wrapper class Integer each hold one int, instances
of Character hold a
char, etc. To store a non-object value in a collection,
create a wrapper object to hold the non-object value, then store the wrapper
in
the collection. For example
Integer intWrapper = new Integer( 3 );someList.addItem( intWrapper );
To retrieve the non-object value from the collection, retrieve the wrapper and then extract the non-object from the wrapper. For example
Integer wrappedInt = (Integer) someList.getFirst();int retrievedInt = wrappedInt.intValue();
(The notation (Integer) before someList.getFirst() in
this example is a cast that tells the Java compiler that
this particular use of getFirst will return
an Integer object. Casts are often used when retrieving data from
collections, because the retrieval message is usually declared to return some
very generic
class— e.g., Object — but client programmers often
know much more precisely what classes their application stores in the collection.
See appendix
section A.5.2 of Algorithms and Data Structures:
The Science of Computing for more information on casts.)
Here are some common wrapper classes from the Java class library.
Every wrapper class provides a constructor that takes a single value of the
corresponding non-object type as its only parameter. Every wrapper class
also handles a parameterless message for extracting the non-object value from
a wrapper, as indicated in the following table (the examples above of
wrapping and unwrapping an int illustrate how one might use these
constructors and extractors).
| Non-Object Type | Wrapper Class | Extraction Message |
|---|---|---|
| int | Integer | intValue |
| long | Long | longValue |
| double | Double | doubleValue |
| float | Float | floatValue |
| char | Character | charValue |
| boolean | Boolean | booleanValue |
For more information on these (and other) wrapper classes, see the Documentation for the Standard Java Library at http://java.sun.com/j2se/1.4.2/docs/api/index.html.
Write Java programs that solve the following problems. Each problem corresponds to a separate program. The programs are simple; each will probably consist of only a main method.
Write a program that reads strings from its user, and builds a list from those strings. After the user has entered the last string, the program should save the list it has built to a file.
Use any technique you are comfortable with to read the strings from the user. Similarly, use any strategy you like for determining when the user has entered the last string.
The name of the file in which to save the list may also be read from the user, or it can simply be a constant in the program.
Write a program that reads a list of strings from a file, and prints it for the user to see. Then the program should remove all occurrences of your name from the list. Finally, the program should print the edited list and save it back into the file from which it came.
The program that creates and saves a list will probably be helpful for building files with which to test this program.
The name of the file that contains the list can be read from the user, using any convenient input technique. Alternatively, the file name can be provided as a constant in the program.
Write a program that creates two lists. One should contain the integers between 1 and 10, in that order, and the other the real numbers 0.1, 0.2, and 0.3 (in order). Finally, create a third list that is the concatenation of these two, without changing the contents of either of the original lists. Print all three lists to verify that each contains what it should, in the order it should, and that the originals have not been altered by the concatenation.
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.
This lab is due on November 1. Turn in printouts of the programs you wrote, along with a description of the inputs on which you tested each (this description can be in comments in the files, or on a separate sheet of paper).
In addition to the programs and descriptions of testing, write a roughly one-paragraph discussion of how programming with lists (and, presumably, other collections) is similar to and/or different from object oriented programming you have done in the past. This needn’t be a comprehensive dissertation on programming with collections compared to other programming, it will be fine if you just describe an example or two of similarities and/or differences you noticed while doing this exercise.
Portions copyright © 2004. Charles River Media. All rights reserved.
Revised Oct. 21, 2004