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