views:

350

answers:

5

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.

+5  A: 

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.

cletus
Yes, I understand that it would be silly to reallocate after removing one element. But what if I add a million elements, and then remove all of them but one, and never add anything till the program is ended. It would be a waste of memory to keep a million-cell array instead of the default size.
cka3o4nik
@cka3o4nik: it's only an array of references. A million of them still takes up only about 4MB - not really worth worrying about such a rare case.
Michael Borgwardt
@cka304nik as Michael says, reducing the array size isn't viewed as a large problem. If you do want to do this however you can call `ArrayList.trimToSize()`.
cletus
Thank you for your explanations.
cka3o4nik
+1  A: 

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.

Bytecode Ninja
A: 

There is not much gain by resizing the ArrayList internal array, even you are using ArrayList to hold a large object.

List<LargeObject> list = new ArrayList<LargetObject>();

list will only hold reference to LargeObject instance, and not holding LargeObject instance itself.

Reference doesn't consume much space. (Think it as pointer in C)

Yan Cheng CHEOK
A: 

The array size is never reduced automatically. It's very rare to actually have a list that is first filled with a large number of elements, then have it emptied but still kept around. And keep in mind that there must have been enough memory to hold the list (which consists only of references) and its elements - unlikely then that the memory consumed by the empty list would be a problem.

If you really encounter an algorithm bizarre enough that this becomes a problem, you can still free the memory by calling trimToSize() manually.

Michael Borgwardt
Good points, thanks.
cka3o4nik
A: 

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.

cHao
I ended up copying the ArrayList source code into my test project and added a getCapacity() method to get to the underlying array. As you guys predicted, it never goes down unless I request it manually by trimToSize(). Thanks.
cka3o4nik