Introduction to Lists Lab

Site Index

These notes provide suggestions for teaching the “Introduction to Lists” laboratory exercise.

Design Goals

This exercise is a simple introduction to lists and collections. It is intended to be used in situations where students need a very gentle introduction to collections, for example when the schedule of a course is such that students’ first exposure to lists and collections is through direct experience in the lab rather than through reading and lectures. If students have had an opportunity to read or talk about material beyond section 11.3 of Algorithms and Data Structures: The Science of Computing, then one can do a more ambitious first lab on lists than this one.

This exercise deliberately does not ask students to create subclasses of List, in order to avoid the intricacies of creating List subclasses (e.g., the makeNewList method and heavy use of casts).

Nonetheless, this exercise exposes students to several features of Java (and other popular object oriented programming languages) that may not have figured prominently in students’ previous experience. Generally, these are features that are somehow connected with collections. They include…

• Wrapper classes and the fact that Java has both object and non-object data types.
• Use of abstract classes such as Object to allow a collection to store arbitrary types of data.
• Some exposure to casts. (The code for this lab doesn’t require casting, but the example of retrieving a wrapper object in the student directions uses a cast, and students who store strings in a list and then try to retrieve them into a string variable may see a compiler error message that refers to casting.)

The Exercises

The “Create and Save a List” exercise requires reading text from the keyboard. This is a complicated thing to do in Java, although we find that the JOptionPane class in the Java class libraries makes it relatively easy. Instructors may also have a favorite third-party library that students can use.

The “Retrieve and Alter a List” exercise introduces students to most of the basic operations on lists: extracting elements, testing for emptiness, adding and removing elements, etc. It also helps students understand how the second element of a list can be accessed as the first element of the list’s tail (a point that generalizes to accessing other elements, and a starting point for understanding the recursive structure of lists).

Both “Create and Save a List” and “Retrieve and Alter a List” introduce the List class’s input and output methods. These methods are not central to the notion of list developed in Algorithms and Data Structures: The Science of Computing, and so are not discussed in the text. However, they (and analogous methods for other data structures) are pragmatically important ways for instructors to distribute test data structures to students, or for student programs that build large data structures to save them between runs. Getting students used to working with these methods is thus a valuable benefit of this exercise.

We included the “Create and Concatenate Lists” exercise in order to help students appreciate the significance of destructive operations on data structures. The naive way to solve this problem is to create the two lists, and then concatenate the second onto the first. But this will change the first list, violating the requirement that neither of the original lists change. Encourage students to print the two original lists after concatenating, to test that they have really done the concatenation without destroying the original lists.

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 9, 2005 by Doug Baldwin

Site Index