Hands On Java Lab 13 Experiment 2 Experiment 2: Appending 1 Value to a Container of Size n 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. Analysis of Experiment 2 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: allocates a new node to store the new value, stores the value in the node, and attaches the node to the LinkedList using the last node, and updates the size of the LinkedList. 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 allocate a new array that is bigger than the old array (typically by doubling the current capacity): copy the existing values from the old array to the new array: place the new value at the next position in the new array: update the members of anArrayList: since no one has a reference to the old array Java will eventually perform garbage collection and reclaim the space: 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. Back to the Exercise List Forward to the Next Experiment Back to the Table of Contents Back to the Introduction Copyright 2000 by Prentice Hall. All rights reserved.
