Removing elements from ArrayList

Use an Iterator and call Iterator.remove() instead.

Iterator it = myList.iterator();
while(it.hasNext()) {
    if (it.next().contains("foo")) { 
        it.remove();
    }
}

This way you will also avoid trouble for reducing the size of the list while relying on it as an exit condition to your loop, and accessing it using indexes that might be varying.

Of course iterating through the list backwards will also work.

The smart way you're looking for is the Iterator interface. For example:

Iterator<String> it = list.iterator();
while (it.hasNext()) {
   String nextItem = it.next();
   if (nextItem.contains("foo")) {
      it.remove();
   }
}

Influenced by Scala and functional programming, I would recommend you to just copy your values to new list for immutability.

List<String> filtered = new ArrayList<String>();
for (String s : myList) {
   if (!s.contains("foo")) {
       filtered.add(s);
   }
}

I would also recommend 2 libs to try out: Guava and lambdaj

ArrayList maintains an array behind the scene. I want to deep into source code of java.util.ArrayList and java.util.LinkedList.

First of all ArrayList maintains an array behind the scenes. Once you create an ArrayList instance it creates an array whose size is 10 and it grows while the elements inserted. It is size grow to 3(size)/2 +1

Here is the source code.

Default size of arrat list. Look at constructer code.

public ArrayList() {
         this(10);
    }

its size grows to 3(size)/2 + 1. here is the source code. ArrayList#ensureCapacity method is called insite ArrayList#add

public void ensureCapacity(int minCapacity) {
         modCount++;
         int oldCapacity = elementData.length;
         if (minCapacity > oldCapacity) {
             Object oldData[] = elementData;
             int newCapacity = (oldCapacity * 3)/2 + 1;
             if (newCapacity < minCapacity)
                 newCapacity = minCapacity;
             // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
        }
     }

When you remove any item from ArrayList. It is removed from the list and other list items is shifted down to the removed items location. Take special attention, reference to this object is set to null and object become eligible to GC, but there is still a reference allocated for ArrayList. The array size behind the ArrayList is same.

Here is the source code

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

As Jon Skeet answered, when an item is removed next item to removed item will be in the removed items location.

However, allocated memory space is the same after removal. java.util.LinkedList is stands for this issue. All items inside LinkedList is dynamicly allocated and deallocated (It is GC's work, of course)

java.util.LinkedList maintains a doubly linked list behind the scenes. Each add and remove operations changes the memory space used by LinkedList. The item is removed and reference to item from its previous and next items is updated.

Here is the source code :

private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
           throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        if (index < (size >> 1)) {
           for (int i = 0; i <= index; i++)
                e = e.next;
       } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
       return e;
   }

I assume that GC collects items as soon as it is removed, i know it is not certain. But removed memory location is a candidate to GC. Please be careful about the reference to the object and the object itself.

Both ArrayList and LinkedList removes items while ArrayList still stores a reference for object types and memory space for primitive types, Linked list also removes references and memory space. At least, references and memory also will be eligible to GC.

After you remove list will automatically shrink.

Suppose you remove element at index 3, that element will be removed, list will shrink and the element that was at index 4 will have index 3 after remove.

You should do this:

for(int i=0; i<myList.size(); i++)
{
    if(myList.get(i).contains("foo"))
    {
        myList.remove(i);
        // as element is removed, next element will have decremented index
        i--;
    }
}

No it won't leaves "empty spaces" in your list, but you will miss removing all required elements from your list.

Lets try to explain with below example. I am having a ArrayList with 4 elements. (a,b,c,d).

for (int i = 0; i < list.size(); i++) {
            if (((String) list.get(i)).contains("c")) {
                list.remove(i);
            }
            if (((String) list.get(i)).contains("b")) {
                list.remove(i);
            }
        }

for (int i = 0; i < list.size(); i++) {
        System.out.print(list.get(i)+" ");
    }

Result: a c d

When traversing the list in forward direction, I tried removing elements (c,b) but still element c is present in my list.

To avoid this we can traverse in backward direction like below.

for (int i = list.size() - 1; i >= 0; i--) {
            if (((String) list.get(i)).contains("a")) {
                list.remove(i);
            }
            if (((String) list.get(i)).contains("c")) {
                list.remove(i);
            }
        }

        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }

Result: b d