Why the element buffer of ArrayList in java is not reduced in size when elements are removed from ArrayList?

Question

Supposed we have pushed n elements in an ArrayList in java. If we remove all elements from this list, still the elementData buffer array of ArrayList is of size of order n, it does not shrink in size as elements are removed from it. Won't it be better if the size of array shrinks as elements are removed from ArrayList?

• Braj: This post might help you.

Answer 1

No, it wouldn't.

Changing the size means actually re-creating the array which is slower than just keeping the potentially unused oversize.

And in addition, if you want to add elements back again and the array is already big enough, it is way faster. Array creation and copying is a very performance intense operation.

See

http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html

I found this question (and answer) which explains a lot about it:

Why Array list increase dynamically and not decrease dynamically

Edit

Referring to 's comment, here a short explanation for the System.arraycopy call in the source code for ArrayList#remove: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.remove%28int%29

public E More ...remove(int index) {
 rangeCheck(index);
 modCount++;
 E oldValue = elementData(index);
 int numMoved = size - index - 1;
 if (numMoved > 0)
 System.arraycopy(elementData, index+1, elementData, index,
 numMoved);
 elementData[--size] = null; // Let gc do its work
 return oldValue;
 }

Well the arraycopy is basically just shifts everything to the left if the index is not the last element. It does not re-create the array.

Let's take a closer look at the exact call:

System.arraycopy(elementData, index+1, elementData, index,
 numMoved);

System#arraycopy expects the following parameters:

public static void arraycopy(Object src,
 int srcPos,
 Object dest,
 int destPos,
 int length)

Source and desination parameters are the same, the elementData (the actual array in the ArrayList). srcPos is index+1 so the copying begins one after the specified index with the number of total elements to move as length argument. desPos is just the index, so thats where our copy will go and this basically just shifts everything right to the specified element to the left, but does not change the array length.

• Braj: ArrayList#remove() method calls System.arraycopy. why? what is does?
• flotothemoon: @user3218114 Can you please send me a link to that reference?
• Braj: It's in source code
• flotothemoon: @user3218114 Added the explanation to my answer. Bascially just array shifting.

Answer 2

Shrinking an array involves allocating a new array and copying all the data over. It can be a costly process.

Also, you can always call trimToSize() if you wanted to recoup space from a ArrayList that has dramatically shrunk. Not sure I have ever seen this called...

• TheLostMind: @SanjeevSharma - What if you need to reinsert the same number of elements?. You will increase the size again?. Shrinking / increasing the size is costly operation.. To improve performance, the size isn't changed.
• Andreas: Imagine a queue underpinned by the list. Would you want to resize the underlying array each time something was popped or pushed?

Answer 3

Performance-wise, it's best if you predefine the size of the ArrayList in the constructor. If the initial size is enough to hold all the items you wish to store in the ArrayList, no resizing is ever required.

If you would resize when removing items, you might reach a size lower than the initial size, which would later require further resizing as you add more item, which would slow down inserts to the list.

Therefore it's best to keep the size of the list equal to the initial size at all times (if possible).

• Braj: The question is more related to remove method.
• Eran: @user3218114 And my answer is that any resizing of the ArrayList capacity is costly (whether it's done in insert or remove and whether is increases or reduces the capacity of the ArrayList).