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. Readn. 1. Create a Timer. 2. Determine the time to appendnvalues to an empty linked list: a. Create an empty linked list. b. Start the Timer. c. For each valueiin the range 0..n-1: Appendito the end of the list. d. Stop the Timer. e. Display the time. 3. Determine the time to appendnvalues to an empty array list: a. Create an empty array list. b. Start the Timer. c. For each valueiin the range 0..n-1: Appendito 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

**constant time**if the time to perform the operation remains the same, regardless of the value of n. The graph of a constant time operation is flat, parallel to the N-axis.**linear time**if the time to perform the operation*is proportional to n*-- describable as c * n, where c is some constant. The graph of a linear time operation is a straight line that rises proportionally to the value of n.**quadratic time**if the time to perform the operation*is proportional to n^2*-- describable as c * n^2, where c is some constant. The graph of a quadratic time operation is a curve that rises as n increases, slowly becoming almost parallel to the Time-axis as n gets very large.

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:

- allocates a new node to store the new value:
- stores the value in the node:
- attaches the node to the
`list`using the previous-node member of the head node (since this always points to the last node), and updates the size of the`List`:

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

Copyright 2000 by Prentice Hall. All rights reserved.