This chapter reviews results from the previous exercise and introduces yet another implementation of the `List`

interface, the doubly linked list.

In the previous exercise, we used `Profiler.java`

to run various `ArrayList`

and `LinkedList`

operations with a range of problem sizes. We plotted runtime versus problem size on a log-log scale and estimated the slope of the resulting curve, which indicates the leading exponent of the relationship between runtime and problem size.

For example, when we used the `add`

method to add elements to the end of an `ArrayList`

, we found that the total time to perform *n* adds was proportional to *n*; that is, the estimated slope was close to 1. We concluded that performing *n* adds is in *O*(*n*), so on average the time for a single add is constant time, or *O*(1), which is what we expect based on algorithm analysis.

The exercise asks you to fill in the body of `profileArrayListAddBeginning`

, which tests the performance of adding new elements at the beginning of an `ArrayList`

. Based on our analysis, we expect each add to be linear, because it has to shift the other elements to the right; so we expect *n* adds to be quadratic.

Here’s a solution, which you can find in the `solution`

directory of the repository:

public static void profileArrayListAddBeginning() { Timeable timeable = new Timeable() { List<String> list; public void setup(int n) { list = new ArrayList<String>(); } public void timeMe(int n) { for (int i=0; ...

Start Free Trial

No credit card required