Java - best way to implement a dynamic-size array of objects

Question

I am a novice with Java.

I have to implement an array of objects that changes in size during execution.

The code I am writing is going to be ported on Android, too.

According to your experience, what's the best class to implement that?

Thanks,
Dan

Answer 1

You should familiar your self with the collection framework in java. You have things like Set, List, Map, SortedSets, etc... Which can be really helpful data structures.

Answer 2

Java has an inadequate template capability. As long as you want an array of objects, then ArrayList<T> is good. For primitives, it's awful.

Assuming you have a hierarchy of objects that you want to put in a list, ArrayList is ideal:

ArrayList<Vehicle> vehicles = new ArrayList<Vehicle>();

vehicles.add(new Car(...));
vehicles.add(new Truck(...));

I'm assuming in the above example that Vehicle is the base class, and Car and Truck are subclasses.

On the other hand, if you want a list of numbers, Java is highly inefficient. Each object is a reference (really a 4 byte pointer) to a 12 byte chunk of memory, plus what you're actually using. Since ArrayList cannot apply to int, this means that creating a list of numbers means:

1. Creating a list of Integer, the object wrapper for int.
2. Converting the objects every time you pull out a number. This is done automatically these days, but it takes time.
3. Initializing 5 times as much storage as needed.

So, if you are manipulating big chunks of primitive data (int, float, double) it can be worth your while writing your own version of ArrayList. This is particularly important when the data is big and the platform is small (like a handheld Android thingy).

Compare this:

ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 1000000; i++)
  list.add(i):

to:

public class IntArray {
private int[] data;
private int used;
private void grow() {
 // implement code to make data double in size here...
}
public IntArray(int size) {
  data = new int[size];
  used = 0;
}

public void add(int i) {
  if (i >= data.length) grow();
  data[used++] = i;
}
}

IntArray list2 = new IntArray(1000000);
for (int i = 0; i < 1000000; i++)
  list2.add(i);

The last time I benchmarked it, the optimal use of the primitive list is more than 10 times faster than the admittedly suboptimal use of ArrayList. To be more fair, pre-allocate the arraylist to be the right size -- it's still way slower.

LinkedList is only worthwhile if you are inserting in the beginning or middle of a list. If your list is being built by adding to the end, ArrayList will thoroughly dominate LinkedList. So for a typical list of objects which you are building up in order, ArrayList is what you are looking for. For a big list of primitives like int or double, write your own list.