New developers sometimes worry about the overhead of these collections and think they should use arrays instead of data structures. To investigate, I wrote a program that creates and accesses 250,000 objects, once through a Java array and again through an ArrayList. This is a lot more objects than most programs use. First the code for the Array version:

import com.darwinsys.util.MutableInteger;

/** Time a bunch of creates and gets through an Array */
public class Array {
    public static final int MAX = 250000;
    public static void main(String[] args) {
        System.out.println(new Array().run(  ));
    }
    public int run(  ) {
        MutableInteger list[] = new MutableInteger[MAX];
        for (int i=0; i<list.length; i++) {
            list[i] = new MutableInteger(i);
        }
        int sum = 0;
        for (int i=0; i<list.length; i++) {
            sum += list[i].getValue(  );
        }
        return sum;
    }
}

And the ArrayList version:

import java.util.ArrayList;

import com.darwinsys.util.MutableInteger;

/** Time a bunch of creates and gets through an Array */
public class ArrayLst {
    public static final int MAX = 250000;
    public static void main(String[] args) {
        System.out.println(new ArrayLst().run(  ));
    }
    public int run(  ) {
        ArrayList list = new ArrayList(  );
        for (int i=0; i<MAX; i++) {
            list.add(new MutableInteger(i));
        }
        int sum = 0;
        for (int i=0; i<MAX; i++) {
            sum += ((MutableInteger)list.get(i)).getValue(  );
        }
        return sum;
    }
}

The Vector-based version, ArrayVec , is sufficiently similar that I don’t feel the need to kill a tree reprinting its code; it’s online.

How can we time this? As covered in Section 25.6, you can either use the operating system’s time command, if available, or just use a bit of Java that times a run of your main program. To be portable, I chose to use the latter, on an older, slower machine. Its exact speed doesn’t matter, since the important thing is to compare only versions of this program running on the same machine.

Finally (drum roll, please) the results:

$ java Time Array 
Starting class class Array
1185103928
runTime=4.310
$ java Time ArrayLst
Starting class class ArrayLst
1185103928
runTime=5.626
$ java Time ArrayVec
Starting class class ArrayVec
1185103928
runTime=6.699           
$

Notice that I have ignored one oft-quoted bit of advice, that of giving a good initial estimate on the size of the ArrayList. I did time it that way as well; in this example, it made a difference of less than four percent in the total runtime.

The bottom line is that the efficiency of ArrayList is almost as good (75%) as that of arrays. The overhead of objects whose methods actually do some computation will almost certainly outweigh it. Unless you are dealing with millions of objects per minute, you probably don’t need to worry about it. Vector is slightly slower, but still only about two-thirds the speed of the original array version.