ArrayList: how does the size increase?

Question

I have a basic question on Java ArrayList.

When ArrayList is declared and initialized using the default constructor, memory space for 10 elements is created. Now, when I add an 11th element, what happens? Will new memory space be created with 20 (or more) element capacity (this requires copying elements from 1st memory location to new location) OR some thing else?

I checked here. But I didn't find an answer.

Please share the knowledge. Thanks.

Answer 1

A new array is created and the contents of the old one are copied over. That's all you know at the API level. Quoting from the docs (my emphasis):

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

In terms of how it actually happens with a specific implementation of ArrayList (such as Sun's), in their case you can see the gory details in the source. But of course, relying on the details of a specific implementation isn't usually a good idea...

Answer 2

Sun's JDK6:

I believe that it grows to 15 elements. Not coding it out, but looking at the grow() code in the jdk.

int newCapacity then = 10 + (10 >> 1) = 15.

/**  * Increases the capacity to ensure that it can hold at least the  * number of elements specified by the minimum capacity argument.  *  * @param minCapacity the desired minimum capacity  */ private void grow(int minCapacity) {     // overflow-conscious code     int oldCapacity = elementData.length;     int newCapacity = oldCapacity + (oldCapacity >> 1);     if (newCapacity - minCapacity < 0)         newCapacity = minCapacity;     if (newCapacity - MAX_ARRAY_SIZE > 0)         newCapacity = hugeCapacity(minCapacity);     // minCapacity is usually close to size, so this is a win:     elementData = Arrays.copyOf(elementData, newCapacity); } 

From the Javadoc, it says this is from Java 2 and on, so its a safe bet in the Sun JDK.

EDIT : for those who didn't get what's the connection between multiplying factor 1.5 and int newCapacity = oldCapacity + (oldCapacity >> 1);

>> is right shift operator which reduces a number to its half. Thus,
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;