Save a copy of Prepend2.java in your project folder. Open Prepend2.java, add it to your project, and take a few moments to examine what it does. What we want it to do is as follows:
0. Read n.
1. Create a Timer.
2. Determine the time to prepend 1 value to a linked list of size n.
a. Define a linked list of size n.
b. Start the Timer.
c. 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 1 value to an array list of size n.
a. Define an array list of size n.
b. Start the Timer.
c. Insert 1 at the beginning of the array list.
d. Stop the Timer.
e. Display the value of the Timer.
Take a few moments to add the necessary statements to make Prepend2.java reflect this logic.
Compile and link Prepend2.java, and then download and print a clean piece of graph paper. As before, we will 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 results from the previous 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 to your graph indicating what it 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 1 value to a list of length n compared to the time required to prepend 1 value to a vector of length n.
As we have seen in the analysis of the previous experiment, inserting a value at the beginning of a linked list takes constant time. So the time to insert a single value at the beginning of the LinkedList is independent of the size of the List.
For the ArrayList on the other hand, inserting a value at the beginning requires us to copy all the values in the list. So the time to insert a single value at the beginning of the ArrayList is depends on the size of the List. You should thus have observed that this is a linear time operation.
Because such copying is not required for a LinkedList, the LinkedList is generally superior to an ArrayList for problems that require values to be inserted at the beginning or the middle of the container.
