Save a copy of Prepend1.java in your project folder. Open Prepend1.java, add it to your project, and take a few moments to examine what it does. Its basic algorithm is as follows:
0. Read n
1. Create a Timer.
2. Determine the time to prepend n values to an empty linked list:
a. Define an empty linked list.
b. Start the Timer.
c. For each value i in the range 0..n-1:
Insert 1 at the beginning of the linked list.
d. Stop the Timer.
e. Display the value of the Timer.
3. Determine the time to prepend n values to an empty array list:
a. Define an empty array list.
b. Start the Timer.
c. For each value i in the range 0..n-1:
Insert 1 at the beginning of the array list.
d. Stop the Timer.
e. Display the value of the Timer.
Compile and link Prepend1.java, and download and print a clean piece of graph paper. As before, we will be plotting the times for the values 5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000 and 50000 (unless your instructor has alternative values for you to use).
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 results from the previous two experiments. Label your sentence Prediction.
As before, begin by running the program using the value 50000, and use the 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 linked list times, and circling those corresponding to array list times. Add a legend to your graph to indicate which line goes with which object, and a title describing what the graph shows.
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 prepend n values to an empty linked list compared to the time required to prepend n values to an empty array list.
Let's use the preceding information to see what happened in Experiment 3. We began with an empty LinkedList:
aLinkedList = new LinkedList();
which we saw before looks like this:
We then used add() to prepend a value to this list:
aLinkedList.add(0, new Integer(i));
and repeated this operation n times. Similar to what we saw in Experiment 1, the add() method simplistically:
It follows that prepending one value always takes these three steps, so that an add() at position 0 takes constant time for a LinkedList. If prepending one value takes constant time, prepending n values should take time proportional to n, or linear time, which should be what you observed in this experiment.
Let's compare what happens when the add() is used on a ArrayList. We began with an empty ArrayList:
anArrayList = new ArrayList();
which we have seen looks like this:
We then used add() to prepend n values to it:
anArrayList.add(0, new Integer(i));
and called this method n times.
It should be evident that the add() operation must move elements to make room for the new value. Suppose we have two values already in the list:
and then add the new value at the beginning:
It should be evident that having to copy the n values has linear timer.
However, unlike adding at the end, we must do the copy every time we do a prepend to make room for the new value. Put differently, each pass through our loop calls add() which must copy n values, and since our loop runs n times, the entire operation requires time proportional to n2. Inserting n values at the beginning of an ArrayList is thus a quadratic time operation, as you should have experienced.
As you experienced, quadratic time operations are very expensive, and should be avoided whenever possible. For this reason, problems that involve any significant number insertions at any position other than the end of the container should be done using the LinkedList, not the ArrayList.
Forward to the Next Experiment