Java how to remove element from List efficiently

Question

Ok, this is a proof-of-concept I have on my head that has been bugging me for a few days:

Let's say I have:

List<String> a = new ArrayList<String>();
a.add("foo");
a.add("buzz");
a.add("bazz");
a.add("bar");

for (int i = 0; i < a.size(); i++)
{
    String str = a.get(i);
    if (!str.equals("foo") || !str.equals("bar")) a.remove(str);
}

this would end up with the list ["foo", "bazz", "bar"] because it would read the string at index 1 ("buzz"), delete it, the string at index 2 ("bazz") would jump to index 1 and it would be bypassed without being verified.

What I came up with was:

List<String> a = new ArrayList<String>();
a.add("foo");
a.add("buzz");
a.add("bazz");
a.add("bar");

for (int i = 0; i < a.size(); i++)
{
    String str = a.get(i);
    boolean removed = false;
    if (!str.equals("foo") || !str.equals("bar"))
    {
        a.remove(str);
        removed = true;
    }
    if (removed) i--;
}

It should work this way (atleast it does in my head lol), but messing with for iterators is not really good practice.

Other way I thought would be creating a "removal list" and add items to that list that needed to be removed from list a, but that would be just plain resource waste.

So, what is the best practice to remove items from a list efficiently?

Might be a duplicate of http://stackoverflow.com/questions/2043783/how-to-efficiently-performance-remove-many-items-from-list-in-java?rq=1 — Khaelex, Apr 07 '14 at 16:53
indeed i could remove the 2nd if, but when i thought of it it had multiple if's to remove items from the list, so that's why i thought of the bool and the 2nd if — DarkW, Apr 07 '14 at 16:55
Other than issue with index. Are you sure about the (!str.equals("foo") || !str.equals("bar")) . to me this conditoin always pass. — Mani, Apr 07 '14 at 17:37
@mani you're right, it should be && instead. As i said that is a proof-of-concept code, not real code, so i missed that. — DarkW, Apr 07 '14 at 17:44

score 3 · Answer 1 · edited May 23 '17 at 12:05

Use an Iterator instead and use Iterator#remove method:

for (Iterator<String> it = a.iterator(); it.hasNext(); ) {
    String str = it.next();
    if (!str.equals("foo") || !str.equals("bar")) {
        it.remove();
    }
}

From your question:

messing with for iterators is not really good practice

In fact, if you code oriented to interfaces and use List instead of ArrayList directly, using get method could become into navigating through all the collection to get the desired element (for example, if you have a List backed by a single linked list). So, the best practice here would be using iterators instead of using get.

what is the best practice to remove items from a list efficiently?

Not only for Lists, but for any Collection that supports Iterable, and assuming you don't have an index or some sort of key (like in a Map) to directly access to an element, the best way to remove an element would be using Iterator#remove.

thanks, but in that case shouldn't it be easier to use a while loop? like: Iterator it = a.iterator(); while (it.hasNext()) { String str = it.next(); // code } — DarkW, Apr 07 '14 at 16:58
@DarkW you can use a `for` or a `while` to navigate through the elements of an `Iterator`. Use the approach you feel more comfortable with. — Luiggi Mendoza, Apr 07 '14 at 17:00

T.J. Crowder · Accepted Answer · 2014-04-07T16:56:02.197

You have three main choices:

Use an Iterator, since it has that handy remove method on it. :-)

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (/*...you want to remove `it.next()`...*/) {
        it.remove();
    }
}

Loop backward through the list, so that if you remove something, it doesn't matter for the next iteration. This also has the advantage of only calling list.size() once.
```
for (int index = list.size() - 1; index >= 0; --index) {
    // ...check and optionally remove here...
}
```

Use a while loop instead, and only increment the index variable if you don't remove the item.

int index = 0;
while (index < list.size()) {
    if (/*...you want to remove the item...*/) {
        list.removeAt(index);
    } else {
        // Not removing, move to the next
        ++index;
    }
}

Remember that unless you know you're dealing with an ArrayList, the cost of List#get(int) may be high (it may be a traversal). But if you know you're dealing with ArrayList (or similar), then...

score 1 · Answer 3 · answered Apr 07 '14 at 16:49

Your first example will likely cause off-by-one errors, since once you remove an object your list's indexes will change. If you want to be quick about it, use an iterator or List's own .remove() function:

Iterator<String> itr = yourList.iterator();
while (itr.hasNext()) {
    if ("foo".equals(itr.next()) {
        itr.remove();
    }
}

Or:

yourList.remove("foo");
yourList.removeAll("foo"); // removes all

score 1 · Answer 4 · answered Apr 07 '14 at 17:26

1

ArrayList.retainAll has a "smart" implementation that does the right thing to be linear time. You can just use list.retainAll(Arrays.asList("foo", "bar")) and you'll get the fast implementation in that one line.

answered Apr 07 '14 at 17:26

Louis Wasserman

191,574
25
345
413

Java how to remove element from List efficiently

4 Answers4