Laboratory Exercise

Introduction to Lists

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)

Purpose

This exercise introduces the basic operations on lists, and exposes students to collection classes.

Prerequisites

Understanding of basic list definitions and operations, as described in sections 11.1 through 11.3 of Algorithms and Data Structures: The Science of Computing.

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

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

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

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 the real numbers 0.1, 0.2, and 0.3. 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.

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.