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 stackoverflow.com/questions/2043783/… — Khaelex
– Khaelex, Commented Apr 7, 2014 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
– DarkW, Commented Apr 7, 2014 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
– Mani, Commented Apr 7, 2014 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
– DarkW, Commented Apr 7, 2014 at 17:44

Community · Accepted Answer · 2017-05-23 12:05:22Z

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<String> it = a.iterator(); while (it.hasNext()) { String str = it.next(); // code }
@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.

T.J. Crowder · Accepted Answer · 2014-04-07 16:56:02Z

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...

Rogue · Accepted Answer · 2014-04-07 16:49:54Z

1

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

answered Apr 7, 2014 at 16:49

Rogue

11.5k6 gold badges51 silver badges74 bronze badges

Comments

Louis Wasserman · Accepted Answer · 2014-04-07 17:26:17Z

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 7, 2014 at 17:26

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

Collectives™ on Stack Overflow

Java how to remove element from List efficiently

4 Answers 4

2 Comments

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Linked

Related