ArrayList of arrays vs. array of ArrayLists vs. something similar

Question

I'm creating a TableModel which will have a fixed number of columns, but the number of rows will be changing (mostly, increasing as function of time). Which would be better approach to store the data,

ArrayList[] columns = new ArrayList[numberOfColumns];
// Each array element is one column. Fill each of them with a new ArrayList.
...
public Object getValueAt(int row, int column) {
    return columns[column].get(row);
}

i.e. creating an array of ArrayLists, each ArrayList representing one column, or:

ArrayList<Object[]> rows = new ArrayList<Object[]>();
// Each ArrayList element is one row.

public Object getValueAt(int row, int column) {
    return rows.get(row)[column];
}

i.e. creating one ArrayList that holds arrays, each of which represent one row.

Any ideas which of these is more efficient in terms of speed or storage? Alternative 1 requires extending N ArrayLists with each added row, while alternative 2 requires extending just one ArrayList but also creating a new array of length N (to represent the new row). Or is there an obvious, better solution?

Solution 1

If the number of columns is fixed then your data is probably row-oriented or at least row-variable at which point each row should be an array. Fixed numbers of columns means you don't need to reallocate your array.

So your structure is:

List<Object[]> rows;

where the array element is one row.

There are several options for what your row object should be however:

1. An array;
2. A List or other Collection; or
3. A custom object.

(3) can probably be done by using some kind of interface that allows you to query the number, type and name of columns.

Solution 2

How about using a single ArrayList itself and accessing element like this

public Object getValueAt(int row, int column) { 
    return data.get(row*NUMBER_OF_COLUMNS+column); 
} 

In this case, each ArrayList object is a cell in a table. And you need not require any other extra structure

Solution 3

Personally, I'd go for an ArrayList of fixed-length arrays. If you're talking about a large quantity of rows, this may be more space efficient (and perhaps faster) than allocating a bunch of ArrayLists, which starts out backed by an array of length 10. Thus, if you have fewer columns than 10 you'll end up with wasted space. On the other hand if you have more, then the ArrayList will have to resize its backing array when you add additional columns.

Edit: actually, you can set the capacity in ArrayList's constructor, so I guess it may not make much difference: http://java.sun.com/j2se/1.5.0/docs/api/java/util/ArrayList.html

Solution 4

I would go with option #2 for several reasons

First, arrays have a fixes length whereas ArrayList are flexible. Given that your #columns is fixes it seems natural to have array per row.

Option #1 is dangerous because it incurs the implicit requirement that all ArrayLists will be of the same length. You may accidentally neglect to add to any one of them thereby creating a bug. You will not have this problem in option #2.

Finally, it seems that the common convetion is that you first index the rows and only then the columns.

View more solutions