Lab 12: Instructor's Notes


This exercise uses a Timer class to time various operations on a ArrayList, and compare them with the times to perform the same operations on a LinkedList. In this way, students will directly experience the time difference of the same operation on the two containers. The exercise introduces analysis of algorithms, and computational complexity.

The exercise runs the operations on problems of size n, with n ranging from 5000 to 50000 in increments of 5000. These values are somewhat arbitrary and appropriate values will vary with your CPU and memory. (e.g., An experiment will likely "crash" if you exhaust your machine's memory.) You should do each of the exercises ahead of time on your lab's machines in order to select an appropriate range of values for n, and inform your students of any changes.

The exercise consists of four experiments, conducted using four different programs:

  1. Appending n values to each container (Append1.java);
  2. Appending 1 value to each container of size n; (Append2.java);
  3. Prepending n values to each container; and (Prepend1.java);
  4. Prepending 1 value to each container of size n. (Prepend2.java);

Each experiment makes use of the class Timer in the ann package.

If you are still using Java 1.1, you can use the classes RetroArrayList and RetroLinkedList instead of ArrayList and LinkedList respectively. They are in the files RetroArrayList.java and RetroLinkedList.java.


Back to This Lab's Table of Contents

Forward to the Prelab Questions


Back to the Table of Contents

Back to the Introduction


Copyright 2000 by Prentice Hall. All rights reserved.