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?

Zeta

Good question. Do you want to be able to change the number of rows and/or columns easily? Additionally, do you want to allow rows to have varying length columns? Edit: my bad, I didn't fully read the first part of your question. – Polyploid

Yep, the number of columns is fixed, but the number of rows is changing. – Zeta

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

Colum

Thanks, I think this is the cleanest solution after all. – Zeta

Of course doing the Object array will cause boxing and unboxing of the data being put into it. That is a pretty big drawback. – Etalon

Answer 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

Councilman

This might indeed be the most efficient alternative - although not the most readable. – Zeta

I mean that, for instance, removing rows requires calculating proper indexes to data, which requires some thought, and screw it up once and the whole data structure is ruined :-) And understanding that code requires a bit more effort - but not that much, anyway. – Zeta

yeah.. i understand... But like you said, its not a very big deal. Definitely doable. :) – Councilman

IMHO flattening what is basically a 2D array into a single dimension is an unnecessary micro-optimization at the expense of code readability. Also you have to be careful not to leave the data in an inconsistent state. Like if you have 8 columns and an exception occurs when you're adding the fifth to the backing list. – Colum

@Joonas: No, this might not be efficient as you thought. In term of storage, there is a "grow factor" (x1.5 of current size) which affects the number of allocation elements whenever the list has to increase its capacity. In term of speed, row removing is nightmare and column sorting is mid-nightmare... I would choose cletus solution above in this case. – Garver

Answer 3

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.

Pleasurable

Answer 4

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

Polyploid