Gab De Jesus Gab De Jesus - 19 days ago 5
Java Question

Copying an array or forcing an initial size on ArrayList. What is more efficient?

I'm trying to make a mutable list (list in a non programming sense) of values. The list is to be a predecided length

n
.

My first choice was to use an array initialized to
n
. But since an array isn't mutable, the only choice I have if I want to add another value is to copy the array into an array of bigger size. I decided to try using an
ArrayList
instead.

Then the trade off is that I can't set the
ArrayList
to an initial size
n
. However, I can add values to the
ArrayList
, since it's mutable. So I'm wondering whether it would be more efficient to create an array then copy it into a bigger array when needed, or to make an
ArrayList
and 'initialize' all the
n
values with a for loop.

What would be better to use?

Answer

Have a look at the implementation of ArrayList is does exactly what you suggest. It simply creates a bigger array whenever needed and copies all the entries form the small array.

This is quite efficient as long as the copy task must only be performed rarely and on not too big arrays. This is why you should always try to create an ArrayList with a size parameter that is about the size you expect that the list will grow to (or a bit bigger). This way you can minimize (or maybe avoid) the replacement of the internal array by a bigger one and all the effort it takes (the array copy).

P.s.
If your data is of an elementar data type you might want to avoid the overhead (memory and speed) of boxing into wrapper types. In this case ArrayList is not suitable for you and you might either implement a similar mechanism for the elementar data type you need it for or have a look at the www. I bed there are plenty implementations like this around there.

P.p.s
If you are unsure about the performance of different approaches, it is always a good idea to implement both and profile the performance for test data that are as close to your real data as possible.