[ACCEPTED]-Does the capacity of ArrayList decrease when we remove elements?-arraylist

It doesn't decrease this automatically. From 4 the doc.

    public void trimToSize() 

Trims the capacity of this ArrayList 3 instance to be the list's current size. An 2 application can use this operation to minimize 1 the storage of an ArrayList instance.

There are several remove methods within 7 arraylist, I will use the remove by index 6 version as this example

 public E 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;

 }

The most important 5 thing to note is that a new array is never 4 created within elementData so its size does not change, only 3 elements are copied.

If you need to reduce 2 the capacity of the array list (which you 1 usually won't) use trimToSize()

The ArrayList offers a method, trimToSize(), that 7 "Trims the capacity of this ArrayList 6 instance to be the list's current size. An 5 application can use this operation to minimize 4 the storage of an ArrayList instance." See 3 http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#trimToSize().

If any other methods do such an action 2 silently, that would depend on the implementation 1 provided with your JRE.

do the the capacity decrease when we remove the object from ArrayList.

The answer is simply no.If you observe source 3 code of the ArrayList class, you will get the answer.
There 2 is no operation to decrease capacity of 1 ArrayList's remove() method.

From what I understand the capicity of an 15 ArrayList is only increased, to decrease 14 it must copy one array to another.

I have 13 tried my own experiment to answer you question. You 12 can't lookup the current capacity of an 11 array list so I am running the garbage collector 10 and checking free memory.

My results are:
             Before:  125637904
         After Aloc:  126959888 -1321984
       After Insert:  126718560 241328
        After Clear:  126958496 -239936
         After trim:  126998432 -39936
      After nullify:  126998400 32

Which is weird 9 and I can't explain. Allocating the list 8 reduced free memory. Inserting into the 7 list increased free memory (I didn't expect 6 that) Clearing the list reduced free memory 5 (???) trimming the list decreases free memory 4 again (doesn't seem to clear it) and setting 3 the list pointer to null should get us back 2 to where we started but it doesn't!

My code 1 is below:

package metcarob.com.dev.rubbish;

import java.util.ArrayList;
import java.util.List;

public class ArrayListTest {

    private static long outputMem(String pre, long last) {
        Runtime.getRuntime().gc();
        String pre2 = "                    " + pre;
        System.out.print(pre2.substring(pre2.length()-20) + "  ");

        long tv = Runtime.getRuntime().freeMemory();

        System.out.print(tv);

        if (last!=0) {
            System.out.print(" " + (last - tv));
        }

        System.out.println("");

        return tv;
    }

    public static void main(String[] args) {

        long lm = outputMem("Before:",0);

        ArrayList<String> lis = new ArrayList<String>();
        lis.ensureCapacity(10000);

        lm = outputMem("After Aloc:", lm);

        for (int c=0;c<10000;c++) {
            lis.add(new String("ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC"));
        };

        lm = outputMem("After Insert:", lm);

        lis.clear();

        lm = outputMem("After Clear:", lm);

        lis.trimToSize();

        lm = outputMem("After trim:", lm);

        lis = null;

        lm = outputMem("After nullify:", lm);

    }

}

You asked about performance implications. You 16 have to clarify what you mean by "decreasing" performance. If 15 you had to resize the array every time that 14 you decreased the array, you would end up 13 re-copying the array each time. On the other 12 hand, if the capacity remains the same, then 11 you are taking up unneeded memory.

It is 10 your use-case which determines how this 9 impacts the performance perceived by the 8 user. Are they running on a machine with 7 low memory? Are we talking about large, mostly 6 static arrays? Is the array changing all 5 the time?

The Java implementation only changes 4 the underlying array if it needs to. This 3 favors avoiding unnecessary copies at the 2 expense of memory size. But, they give you 1 ability to trim it if necessary.

Does the capacity of an ArrayList decrease when we 49 remove elements?

No. This is an implementation detail, but AFAIK 48 no (standard) implementation of the ArrayList class 47 has ever reduced the capacity automatically 46 of a list automatically when elements are 45 deleted.

If the ArrayList capacity doesn't decrease, could 44 this lead to performance issues?

Well, in 43 general no.

Firstly, lists typically don't shrink. (Most 42 lists have a relatively short lifetime. They 41 are treated, built by appending and then 40 processed. List element removal is relatively 39 unusual ... though it depends on the application.) So 38 the question is moot, most of the time.

Secondly, unless 37 a ArrayList is grossly oversized, then the unused space 36 at beyond the end of the list doesn't impact 35 performance significantly. Indeed the only 34 time when anything is directly impacted 33 at all is when the list is marked and copied 32 by the garbage collector. And the impact 31 is relatively small, because the region 30 beyond the logical end of an ArrayList is always 29 cleared to null to prevent memory leaks.

It is 28 worth noting that an ArrayList that is creating by 27 appending to an initially empty list is 26 liable to have a backing array that is on 25 average 50% too big. This is because ArrayLists 24 builtin strategy for expanding the backing 23 array is to double its size. This what 22 makes append an amortized O(1) operation.

Thirdly, a 21 delete or similar operation doesn't "know" what 20 is going to happen next with the list, so 19 it cannot judge whether resizing is an appropriate 18 thing to do.

If your application really needs to, it 17 could call trimToSize() after deleting elements. However, beware:

1. Calling 16 trimToSize() is expensive. The ArrayList implementation is going 15 to create a brand new backing array (of 14 exactly the right size) and copy all of 13 the array elements.

2. The next time you insert 12 or append an element to the ArrayList after a trimToSize(), the 11 operation will be forced to reallocate the 10 backing array ... again. And the new capacity 9 will be double the current list size.

In 8 fact, if you think about it automatically 7 shrinking an ArrayList after each deletion is pretty 6 much guaranteed to be BAD for performance 5 due to the reallocations and copying it 4 would trigger.

Insertion and deletion would 3 become significantly more expensive than 2 it currently is, and for some usage patterns 1 append would become O(N) on average.