What is the most efficient method to remove an item from Arraylist?

Question

I would like to know which of the methods available by the class ArrayList is more efficient to delete an item from the list.

Answer 1

The two forms provided by the class ArrayList sane:

meuArrayList.remove(indice);

Where indice is the position of the item in the list or:

meuArrayList.remove(elemento);

Where elemento is an exact occurrence of any element that is on the list.

Observing: the second way will only work properly if your list is of some kind native to java (like String, Integer, etc...). If you create your own objects, this method will only work correctly overwriting the method equals(). In this reply explains how do it properly.

According to the source code of the methods remove(index) and remove(Element), you can notice that the first option does not go through the entire list, removing directly in the element index, while the second will go through until you find the first occurrence of the last element to remove.

Follow the code to test the difference:

import java.util.ArrayList;

public class ArrayListRemocaoTest {

    public static void main(String[] args) {

        System.out.println("- Removendo o primeiro item/indice");       
        executarTeste("0");
        System.out.println();
        System.out.println("- Removendo um item/indice intermediario");
        executarTeste("5000");
        System.out.println();
        System.out.println("- Removendo o ultimo item/indice");
        executarTeste("9999");

    }

    private static void executarTeste(String valueIndex) {

        ArrayList<String> array1 = new ArrayList<>(10000);
        ArrayList<String> array2 = new ArrayList<>(10000);

        for(int i = 0; i < 10000; i++){
            array1.add(i+"");
            array2.add(i+"");
        }

        int indice = Integer.valueOf(valueIndex);

        long startTime = System.nanoTime();
        array1.remove(indice);
        long endTime = System.nanoTime();

        double duration1 = (endTime - startTime)/1000000d;

        System.out.println("Tempo de remoção do remove(index)(ms): " + String.format("%.3f", duration1));       

        startTime = System.nanoTime();
        array2.remove(valueIndex);
        endTime = System.nanoTime();

        double duration2 = (endTime - startTime)/1000000d;

        System.out.println("Tempo de remoção do remove(Element)(ms): " + String.format("%.3f", duration2));

        System.out.println("Diferença de tempo entre as duas formas: " + String.format("%.3f", (duration2-duration1)));
    }

}

In the above code there are 3 tests I did using the eclipse IDE, with two lists with size of 10,000 items (the code can be tested on ideone). The tests are as follows::

• remove the first element from the lists with the two methods;
• remove an intermediate element (such as Indice 5000) from the lists with both methods;
• remove the last element from the lists with both methods;

And the results of the execution were:

- Removendo o primeiro item/indice
Tempo de remoção do remove(index)(ms): 0,022
Tempo de remoção do remove(Element)(ms): 0,036
Diferença de tempo entre as duas formas: 0,014

- Removendo um item/indice intermediario
Tempo de remoção do remove(index)(ms): 0,014
Tempo de remoção do remove(Element)(ms): 0,673
Diferença de tempo entre as duas formas: 0,659

- Removendo o ultimo item/indice
Tempo de remoção do remove(index)(ms): 0,035
Tempo de remoção do remove(Element)(ms): 1,339
Diferença de tempo entre as duas formas: 1,304

Note that in the three tests, removing by the index was faster, but the time difference is almost derisory. The result varies with each execution, but one can notice a small difference between both.

What really impacts the values of the tests is that in both removal forms, a copy of the list is created, where the index that will be removed from the list is moved to last position, and then applied null in this position, leaving the Garbage Collector do the rest.

Depending on the use of hardware resources at this point in the copy of the list, even more so if it is a large list like the one in the test above, it will affect the test time for more or less time. If you do not want this behavior, maybe the ideal is to use a Linkedlist.