Java: How ArrayList manages memory

Question

In my Data Structures class we have studies the Java ArrayList class, and how it grows the underlying array when a user adds more elements. That is understood. However, I cannot figure out how exactly this class frees up memory when lots of elements are removed from the list. Looking at the source, there are three methods that remove elements:

public E remove(int index) {
 RangeCheck(index);

 modCount++;
 E oldValue = (E) 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;
}

public boolean remove(Object o) {
 if (o == null) {
            for (int index = 0; index < size; index++)
  if (elementData[index] == null) {
      fastRemove(index);
      return true;
  }
 } else {
     for (int index = 0; index < size; index++)
  if (o.equals(elementData[index])) {
      fastRemove(index);
      return true;
  }
        }
 return false;
}


private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, 
                             numMoved);
        elementData[--size] = null; // Let gc do its work
}

None of them reduce the datastore array. I even started questioning if memory free up ever happens, but empirical tests show that it does. So there must be some other way it is done, but where and how? I checked the parent classes as well with no success.

Answer 1

They don't reduce the underlying array. They simply decrement the size. The reasoning for this is that if you have 1000 elements in an array and delete 1, why reallocate and copy the array? It's hugely wasteful for very little gain.

Basically Java ArrayLists have two important properties and it's important to understand they are different:

• size: how many elements are notionally in the List; and

• capacity: how many elements can fit in the underlying array.

When an ArrayList expands, it grows by about 50% in size even if you're only adding one element. This is a similar principle in reverse. Basically it comes down to this: reallocating the array and copying the values is (relatively) expensive. So much so that you want to minimize it happening. As long as the notional size is with a factory of about 2 of the array size, it's just not worth worrying about.

Answer 2

An ArrayList doesn't automatically shrink back, as far as i know. However, you can say something like:

ArrayList al = new ArrayList();

// fill the list for demo's sake
for (int i = 0; i < 1000000; ++i)
{
    al.add(i);
}

// now remove all but one element
al.removeRange(1, al.size());

// this should shrink the array back to a decent size
al.trimToSize();

Note, the amount of memory available probably won't change til the GC runs again.

Answer 3

I have to have another look at ArrayList's source code, but remove removes the object from the array, and then if the object is not referenced to by any other objects, the GC can delete that object. But the array size is not decreased.