Think Data Structures

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