Laboratory Exercise

Lab 8 — Introduction to Lists

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

Purpose

Prerequisites

Background

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.

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

Wrapper Classes

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

To retrieve the non-object value from the collection, retrieve the wrapper and then extract the non-object from the wrapper. For example

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

Named Constants

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

Java programmers can declare named constants (i.e., names that stand for an unchangeable value). Such declarations look almost exactly like initialized variable declarations, except that they begin with the word final. For example, the statement

declares an integer constant whose name is limit and whose value is 100. See “Assignment and Initialization” in section A.2.1 of Algorithms and Data Structures: The Science of Computing for more information on constant declarations. There are several places in this exercise where such declarations will make your code easier to read and write.

Exercise

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.

Create and Save a List

Write a program that creates a list containing the integers from 1 to n, where n is a constant defined in the program. The integers should be in ascending order in the list, i.e., the first element of the list should be 1, the second 2, and so forth until the last element, which is n. After building the list, the program should save it to a file.

You may test your program on whatever n values you like, but it should be easy for a programmer to change n, and the program should work for whatever value the programmer chooses.

The name of the file in which to save the list may be read from the user, or it can simply be another constant in the program.

Retrieve and Alter a List

Write a program that reads a list from a file, and prints it for the user to see. If the list contains at least two items, the program should switch the first two within the list (i.e., make the first item be second, and the second item first) and print the result.

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 from which to retrieve 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.

Create and Concatenate Lists

Write a program that creates two lists. One should contain the integers between 1 and 10, and the other should be a list of strings read from the user. 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, and that the originals have not been altered by the concatenation.

You can use any input technique you like to read strings from the user for the second list. You can also use any technique you like to decide when the user has finished entering strings (e.g., have the user enter a special string such as “STOP” to mark the end of the input, read a predefined number of strings, ask the user before each string if they really want to enter another one, etc.)

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 exercise is due on Monday, March 21. Turn in printouts of each program. In addition to the programs, turn in a couple of sentences discussing ways in which you found programming with containers similar to and different from programming you have done with other sorts of objects. These sentences can be comments in one of your programs, or they can be on a separate sheet of paper.