Alternative Implementations of ArrayList

As discussed in class, an ArrayList utilizes a behind-the-scenes array for the storage of data. The add procedure keeps track of how many elements are available in the current array, and expands that array as needed. The underlying code, based on the generic type E typically includes the following (or equivalent):

    public void add (E e)
    {
       // check if myArray must be expanded
       if (numStored == myArray.length)
          {
              /* the following code follows approach A in the lab */
             E newArray [] = (E[]) new Object [/* new length here */];
             for (int i = 0; i < numStored; i++)
                 newArray[i] = myArray[i];
             myArray = newArray; 
          }

    // insert the given element into myArray
    myArray[numStored] = e;
    numStored++;
    }

Variations in this implementation arise in deciding what new length to utilize when declaring the newArray. Three possible choices are:

• myArray.length + 1
• myArray.length + 10
• 2*myArray.length

In a recent experiment, each of these variations were coded, and the resulting methods timed for adding 1000, 2000, 4000, ..., 128000, and 400000 items to the ArrayList. In these experiments, all code was identical, except the length of the new array .

The timings obtained from the three approaches follow:

  Timings for 3 Implementations of a Generic ArrayList
   using Integer elements

One implementation increases the underlying array by 1 each time
One implementation increases the underlying array by 10 when needed
One implementation doubles the underlying array when needed


Comparison of ArrayList size expansion
Timings for approach 1
    number     cumulative   average time
   additions      time        per add
      1000          1          0.0010
      2000        116          0.0580
      4000        117          0.0293
      8000        119          0.0149
     16000        120          0.0075
     32000        123          0.0038
     64000        128          0.0020
    128000        141          0.0011
    200000        155          0.0008


Timings for approach 2
    number     cumulative   average time
   additions      time        per add
      1000          1          0.0010
      2000          5          0.0025
      4000         63          0.0158
      8000         87          0.0109
     16000        164          0.0103
     32000        435          0.0136
     64000       1507          0.0235
    128000       5635          0.0440
    200000      35260          0.1763


Timings for approach 3
    number     cumulative   average time
   additions      time        per add
      1000          9          0.0090
      2000         49          0.0245
      4000        133          0.0333
      8000        378          0.0473
     16000       1084          0.0678
     32000       3649          0.1140
     64000      14271          0.2230
    128000      58224          0.4549
    200000     347348          1.7367

Work for this Exercise

Review the experimental data.

• Determine which approach corresponds to which of the three options for expanding the length of the array.
• Write a careful argument, drawing upon the data presented, which justifies your conclusions. In each case, consider the cumulative time and the average time for the approach itself, and also compare the times for each approach with those of the others.

created 29 October 2018 revised 29 October 2018
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.