Create a project for this exercise, and save a copy of Append1.java, and the ann package in your project folder. Open Append1.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 append n values to an empty linked list:
a. Create an empty linked list.
b. Start the Timer.
c. For each value i in the range 0..n-1:
Append i to the end of the list.
d. Stop the Timer.
e. Display the time.
3. Determine the time to append n values to an empty array list:
a. Create an empty array list.
b. Start the Timer.
c. For each value i in the range 0..n-1:
Append i to the end of the list.
d. Stop the Timer.
e. Display the time.
Download and print a piece of graph paper. Then compile and link Append1.java. We will be plotting the times for the values: 5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000 and 50000 (unless your instructor has alternate values for you to use).
Begin by running the program for the value 50000, to establish the upper bound for your graph. Using the results, establish the scale on your graph's Time axis, writing in the values for each line on that axis. Then plot the points for n = 50000, drawing a box around the time for the array based list, and a circle around the time for the linked list. Use the program to determine the times for the remaining values, and add those points to your graph.
Graph the time for appending to a linked list by connecting the boxed points, and graph the time for appending to an array based list by connect the circled points. Add a legend to your graph in which you associate the line of boxed points with the linked list, and the line of circled points with the array based list. Then label the graph with the title of the experiment (i.e., Appending n Values to an Empty Container).
Computer scientists categorize the time to perform an operation in any of several ways, depending on how long that operation takes as a function of n, the "size" of the input. Informally, an operation occurs in
There are additional categories (logarithmic, cubic, exponential and factorial time) but these three are all that we will see in our exercise today.
On the back of your piece of "graph paper," write a short paragraph in which you characterize each operation as constant, linear, or quadratic time, plus your general conclusions about the time required to append n values to an array based list compared to the time required to append n values to a linked list, based on the results of this experiment.
Let's use the preceding information to see what happened in Experiment 1. We began with an empty LinkedList:
aLinkedList = new LinkedList();
The structure of the LinkedList is a bit complicated, but each node in the list stores three things: a value, a reference to the previous node (if any), and a reference to the following node (if any). The list itself will store references to the first and last nodes and for convenience the number of nodes in the list. The empty list is thus something like the following:
We then used add() to append a value to this list:
aLinkedList.add(new Long(i))
and repeated this operation n times. The add() function simplistically:
Adding another node will result in:
Thanks to the last reference, add() has direct access to the last node in the list. It follows that appending one value always takes these three steps, so that add() takes constant time for a LinkedList. If appending one value takes constant time, appending n values should take time proportional to n, or linear time, which should be what you observed in Experiment 1.
Let's compare what happens when the add() message is sent to an ArrayList. We began with an empty ArrayList:
anArrayList = new ArrayList();
This kind of list will use an array to store the values. It allocates an array with some initial capacity and when it runs out of space will allocate a larger array and do a copy. The empty ArrayList should look something like this:
We then used add() to append n values to it:
anArrayList.add(new Integer(i));
The add() function member is designed to append values in an efficient manner with respect to time. It should be evident that the add() function may need to increase the size of anArrayList to make room for a new value. If it is necessary, add() will allocate a larger array with more space than is needed currently and copy the old values. In this case, it is not needed and add() writes the new value into the next available location, giving us:
This way, instead of add() causing anArrayList to grow just big enough to hold one more integer, add() instead causes anArrayList to increase in capacity by an amount sufficient to store a large sequence of integers! This is the reason that the size and capacity of a ArrayList are two different quantities: the size is the number of values the ArrayList contains, the capacity is the number of values it can contain!
By allocating more space than is needed, calls to add() will proceed quickly, since the ArrayList will not need to be expanded to accommodate them.
This is the reason appending to ArrayList was relatively fast in Experiment 1 -- most calls to add() are fast, while relatively few calls take longer time to allocate new memory and copy values.
As a result, the time to append n values to an ArrayList should be roughly linear in Experiment 1.
Forward to the Next Experiment