## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Chapter 5. Doubly Linked List

This chapter reviews results from the previous exercise and introduces yet another implementation of the `List` interface, the doubly linked list.

# Performance Profiling Results

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; ...`

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required