3

Java's ArrayList dynamically expands itself when it needs to. How many elements does it add when the expansion happens?

And does it copy the old array into the new one, or does it somehow link the two together?

Barry Brown
  • 20,233
  • 15
  • 69
  • 105

3 Answers3

9

Have a look at the source code:

int newCapacity = (oldCapacity * 3)/2 + 1;

The exact factor differs by implementation, gnu uses a factor of 2. It doesn't matter much, it's just trading memory for speed.

It copies all the elements into a new array.

maaartinus
  • 44,714
  • 32
  • 161
  • 320
4

It creates a new array of double some multiple of the size, and copies the elements over. (I'm not sure if the actual multiplier is specified per the Java standard.)

Now the natural question is, why? Why not just add, say, five elements every time?

It's to make things faster: You add n elements for free, and on element n + 1, you have to copy over the n previous elements into the array of size 2n. So the cost of copying those n elements gets distributed ("amortized") over themselves (since you previously added them for free), and so on average, the cost of adding each element was n/n, or about 1 operation per element.

(See this link for some more discussion on this topic.)

Community
  • 1
  • 1
user541686
  • 205,094
  • 128
  • 528
  • 886
0

Strictly speaking, the exact resizing behavior is not specified in the spec/JavaDoc:

The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

This implies that the internal array can't be resized by adding a constant number, but that some multiplication has to be involved. As maartinus has pointed out the Sun JDK and OpenJDK multiply the size by 1.5 (roughly).

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
  • Do you happen to know why, by any chance? I'm curious as to why they don't double it by default. – user541686 Feb 01 '11 at 07:18
  • 1
    Mehrdad explains the reason why it's multiplied at all. The exact factor is a decision between memory-efficiency and avoiding multiple copies. Using factor 2 could waste too much memory (up to 50% of the array could be unused!). Using a factor closer to 1 (for example 1.1) would mean that the array needs to be copied more often. – Joachim Sauer Feb 01 '11 at 07:22