Save a copy of Append2.java in your project folder. Open Append2.java, add it to your project, and take a few moments to examine what it does. The basic algorithm we want it to perform is as follows:
0. Read n.
1. Create a Timer.
1. Determine the time to append 1 value to a linked list of length n:
a. Create a linked list of length n.
b. Start the Timer.
c. Append 1 to the end of the list.
d. Stop the Timer.
e. Display the value of the Timer.
2. Determine the time to append 1 value to an array list of length n:
a. Create an array list of length n.
b. Start the Timer.
c. Append 1 to the end of the ArrayList.
d. Stop the Timer.
e. Display the value of the Timer.
Append2.java contains a partial implementation of this algorithm. Add the necessary statements to Append2.java to complete the implementation of this algorithm. Then compile and link Append2.java.
Download and print a clean piece of graph paper. We will again be plotting the time for the values 5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000 and 50000 (unless your instructor has alternative values for you). On the back of your piece of "graph paper," write a sentence or two in which you predict what you will observe, based on your experience in Experiment 1. Label your sentence Prediction.
As before, begin by running the program using the value 50000, to establish the upper bounds, and use these results to establish the scale on your graph's Time axis. Then use your program to generate the times for the remaining values, and add points to the graph for these times, boxing those corresponding to LinkedList times, and circling those corresponding to ArrayList times. Add a legend to your graph to indicate which line goes with which object and a title naming the experiment whose results are shown in the graph.
On the back of your piece of graph paper, review your prediction. Write a short paragraph in which you characterize each of these operations as constant, linear or quadratic time, and given any general conclusions you can draw about the time required to append one value to a LinkedList of length n compared to the time required to append one value to an ArrayList of length n.
Let's see what just happened. We filled our list until it had n elements in it. For simplicity, suppose that n is 3, in which case we have a list like this:
We then called add() to append a 1 to aLinkedList:
aLinkedList.add(new Integer(1));
To append a 1 to the LinkedList, the add() operation performs the same three steps it performed in Experiment 1. It:
As before, the time for these three steps is constant and independent of the number of values in the list. Where we appended n values in Experiment 1 (and thus observed a linear time), we are only appending one value in this experiment (and thus observe a constant time).
That is, where appending n values to an empty LinkedList took time proportional to n, appending 1 value to a LinkedList of size n takes constant time, regardless of the size of the LinkedList.
We then defined a ArrayList of size n:
anArrayList = new ArrayList(n);
and then filled it with n values. If we again consider the case where n is 3, we can visualize anArrayList as follows:
Since we were preallocating and then filling the ArrayList in Experiment 2, the size and capacity of anArrayList are both 3.
We then call add() to append a single value to this ArrayList:
anArrayList.add(new Integer(1));
Since the size and capacity of anArrayList are the same, the add() operation must
The times to allocate memory (step 1), store the new value (step 3), and update the members of anArrayList (step 4) are all fairly constant. However, the time to perform the copying in step 2 is proportional to the size of the ArrayList, hence you should have observed a linear time for this operation.
Forward to the Next Experiment