CODEWITHSUNDEEP
javaarraylist
George Herbert
George Herbert

Reputation: 51

Which way of removing elements from an ArrayList is more efficient?

I have the following declarations:

ArrayList<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("2");
list.add("3");
list.add("4");

Now my question is: if I want to remove the "2"s from the list, which way is better?

first way:

for(int i = 0; i < list.size(); i++) {
    if(list.get(i).equals("2")) {
        list.remove(i);
        i--;
    }
}

second way:

Iterator<String> iterator = list.iterator();
    while(iterator.hasNext())
        if(iterator.next().equals("2"))
            iterator.remove();

Are both safed properly and which is more efficient?

Are there any other methods to remove elements from an ArrayList without getting IndexOutOfBounds errors?

Upvotes: 5

Views: 3639

Answers (4)

trutheality
trutheality

Reputation: 23455

Actually, what might be faster is

list.removeAll(Collections.singleton("2"));

Behind the scenes, for an ArrayList, it does basically create a new copy of the array like @Edmund suggests, but at a lower level, which may lead to higher performance.

Still, as others have mentioned, a LinkedList generally has better performance for removing multiple elements from a large list.

(Even if you do decide to switch to a LinkedList you can still use the above code, it will be equivalent to using the iterator method with a little bit of overhead for the singleton collection that's created and for some extra method calls that happen.)

Upvotes: 5

Makoto
Makoto

Reputation: 106390

For individual elements, your for-loop will work fine (well, it will when you remove i-- - the remove() automatically shifts elements over to the left) (No really, it will work fine). So will your iteration method.

You're only iterating to the end of the ArrayList, and you won't step off of it. In terms of efficiency, it's a wash - I would recommend you sample runtimes with sizes of 100,000 and see how it goes. (It's still on the order of O(N) operations, no matter how large the list is.)

Upvotes: 0

Kunal
Kunal

Reputation: 3535

I have read it in some data structure book, that iterator approach is better,

in case of list.remove call under loop, evety time it will start from 0 index to index ot item to remove, then remove element and shift affected elements, it will be o(n2) process.

but in case of iterator.remove, element are removed as they are accessed by iterator without having to go back at beggining of list, thus o(n) process.

Upvotes: -1

Edmund
Edmund

Reputation: 10809

Either way is going to need to shift elements down for each element removed. If your list is really big, it could well be faster to create a new list:

ArrayList<String> newList = new ArrayList<String>();
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String val = iterator.next();
    if(!val.equals("2"))
        newList.add(val);
}

/* Or just return newList, depending on how list is used in subsequent code. */
list.clear();
list.addAll(newList);

You could think about using LinkedList instead of ArrayList. But benchmarking (with realistic use cases) is the best way to find out what's most efficient.

Upvotes: 2

Related Questions