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.

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

Solution 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 ;

Solution 3

It will depend on the implementation, but from the Sun Java 6 source code:

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

That's in the ensureCapacity method. Other JDK implementations may vary.

Solution 4

When we try to add an object to the arraylist,

Java checks to ensure that there is enough capacity in the existing array to hold the new object. If not, a new array of a greater size is created, the old array is copied to new array using Arrays.copyOf and the new array is assigned to the existing array.

Look at the code below (taken from Java ArrayList Code at GrepCode.com).

Edit:

public ArrayList() Constructs an empty list with an initial capacity of ten.

public ArrayList(int initialCapacity) we can specify initial capacity.

public ArrayList(Collection c) Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Now when we use ArrayList() constructore we get a ArrayList with Size=10 On adding 11th element in the list new Arraylist is created inside ensureCapacity() method.

Using following formula:

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

Solution 5

Up to JDK 6 the the capacity grow with formula newCapacity = (oldCapacity * 3/2) + 1.

In JDK 7 and above the formula changes to newCapacity = oldCapacity + (oldCapacity >> 1).

So if initial capacity is 10 then new capacity will be 16 in JDK6 and 15 in above JDK7

View more solutions

Comments

[Shaun the Sheep]

This doesn't add anything that hasn't been said in the original answers from 2010.

[Vikas]

A new array will be created and the contents of the old one will be copied over. so what will happen to old array either it will be in memory or deleted?

[T.J. Crowder]

@VikasKumarSingh: The old one becomes eligible for garbage collection, like any object that no longer has anything referencing it. When (or even if) that happens is up to the JVM.

[VeKe]

that movement :) when you get your answer in google search after nearly 2 years

[Ravi.Kumar]

what happens to the old ArrayList from which the elements are copied? Does GC reclaims that memory?

[T.J. Crowder]

@Ravi.Kumar: There is no old ArrayList, just an old array. Yes, the ArrayList releases its reference to the old array, which is the only reference to it, which means it's eligible for GC.

[Manan Shah]

When you add 11th elements capacity will be 15 not 20.

[ZhaoGang]

yes, reading the source code is the best way to understand the behavior. I have also read the code and got the same answer. This is true for the jdk 8.

[vsriram92]

For the people who can't get the derivation for "1.5". Considering oldCapacity as x, Then newCapacity = x + x/(2^1) = x +x/2 = 1.5x

[JAAAY]

The operator '>>', which does sign extension while shifting, may be a little confusing for the some, because it is not considered to be used as the div operator, due to not working with negative values. In this case it just works due to length being always >=0. As as div operator '>>>' should be used mainly.

[GGO]

Can you add some explanation ? it's a quite short

[Denson]

@T.J. Crowder Is it at all possible(it should be) that allocation of new Array dynamically was not possible as that much memory is not present as contiguous locations? What does Java specify be done in such cases?

[T.J. Crowder]

@Denson - Whenever the JVM can't allocate memory, it either just dies (or is so slow trying to allocate that it may as well have died), or it succeeds in throwing an OutOfMemoryError. Seems to me (from my experience years ago) is that it generally does manage to throw the error (having some memory set aside for that purpose), but YMMV.

[MathMax]

Hi Shobha and Welcome to StackOverflow. Please do not insert your whole answer in a code block. Please use code blocks only for code and leave text outside. Moreover, you might want to test your code before pasting it: you cannot use blank space in a variable name, so current capacity is not a variable and your code won't compile.

[ChristianB]

Welcome to Stack Overflow. What new information does this answer add compared to the other answers?

[Eric Aya]

This is the same as in this other answer.