Most Efficient Way To Delete Elements From Array Lists?

Question

I'm studying OOP, and I came across array lists. I'd like to know how the remove() function actually works, and what is the most efficient way to use it.

First method to delete all the "BB"

public class ArrayListTest {
    public static void main(String args[]){
        ArrayList<String> Alist = new ArrayList<String>();
        Alist.add("AA");
        Alist.add("BB");
        Alist.add("AA");
        Alist.add("AA");
        Alist.add("AA");
        Alist.add("BB");
        System.out.println("Original ArrayList : " + Alist);
        int n = 0 ;
        for (int i = 0; i < Alist.size(); i++){
            n++;
            Alist.remove("BB");
        }
        System.out.println(n);
        System.out.println("Modified ArrayList : " + Alist);
    }
}

The output

run:
Original ArrayList : [AA, BB, AA, AA, AA, BB]
4
Modified ArrayList : [AA, AA, AA, AA]
BUILD SUCCESSFUL (total time: 0 seconds)

Secend Method to delete all the "BB"

public class ArrayListTest {
    public static void main(String args[]){
        ArrayList<String> Alist = new ArrayList<String>();
        Alist.add("AA");
        Alist.add("BB");
        Alist.add("AA");
        Alist.add("AA");
        Alist.add("AA");
        Alist.add("BB");
        System.out.println("Original ArrayList : " + Alist);
        int n = 0 ;
        while(Alist.contains("BB")){
            n++;
            Alist.remove("BB");
        }

        System.out.println(n);
        System.out.println("Modified ArrayList : " + Alist);
    }
}

The output

run:
Original ArrayList : [AA, BB, AA, AA, AA, BB]
2
Modified ArrayList : [AA, AA, AA, AA]
BUILD SUCCESSFUL (total time: 0 seconds)

It's confusing because the counter was triggered to increase a few more times in the first one, but is it actually more efficient, or is the "contains()" looping through the whole array list at each check on the statement behind the scene.

[How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Andy Turner, May 01 '19 at 08:29
Actually, I didn't, and that's exactly what I'm trying to ask.. @Eran — Rami, May 01 '19 at 11:52

Andy Turner · Accepted Answer · 2019-05-01T10:33:54.263

The most efficient way to delete from an arraylist is probably:

Alist.removeAll(Collections.singleton("BB"))

or

Alist.removeIf("BB"::equals)

These methods can be more efficient than individual calls to remove because the actual deletion can be deferred until all elements equal to "BB" have been identified.

This is important because removing an element from an ArrayList shifts all of the elements with larger index "down by one". In the worst case (when all the list elements are equal to the thing you want to remove), individual list removal calls would be quadratic in the number of list elements; removeAll or removeIf would be linear, because they can shift the non-deleted elements just once, and not bother shifting the to-be-deleted elements at all.

The most obvious inefficiency in the first method is that you call remove as many times as there are list elements, irrespective of how many times the item appears in the list. In a particularly pathological example, you could have 1M elements in the list, where none of them are equal to "BB": you'd still call remove 1M times.

The most obvious inefficiency in the second method is that you invoke contains and then remove. You're looking up the element twice by doing this.

A more efficient method - but still less efficient than the two methods at the start of this answer - would be to use the return value of remove, which is a boolean indicating whether an element was actually removed. Once remove returns false, there is no point in calling remove again, because the element isn't found:

while (Alist.remove("BB")) {}

Youcef LAIDANI · Answer 2 · 2019-05-01T08:32:42.923

7

If you are using Java8, all you need is just :

aList.removeIf(s -> s.equals("BB"));

Or as a short way :

aList.removeIf("B"::equals);

If you note, this way not need to check if the element exist or no in the list.

as a good practices :

don't name variables where the first letter is upper case Alist, instead use aList for example

edited May 01 '19 at 08:32

answered May 01 '19 at 08:30

Youcef LAIDANI

55,661
15
90
140

score 0 · Answer 3 · answered May 01 '19 at 10:56

List<String> list1=new ArrayList(Arrays.asList("AA","BB","AA","AA","AA","BB"));
        List<String> list2=new ArrayList();

        list2=list1.stream().filter(a -> !a.equals("BB")).collect(Collectors.toList());
        System.out.println(list2);

This works fine !Check it out.

Most Efficient Way To Delete Elements From Array Lists?

3 Answers3