CODEWITHSUNDEEP
javalist
DarkW
DarkW

Reputation: 595

Java how to remove element from List efficiently

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?

Upvotes: 1

Views: 882

Answers (4)

Louis Wasserman
Louis Wasserman

Reputation: 198591

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.

Upvotes: 1

T.J. Crowder
T.J. Crowder

Reputation: 1075905

You have three main choices:

  1. 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();
    }
}

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

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

Upvotes: 2

Luiggi Mendoza
Luiggi Mendoza

Reputation: 85809

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.

Upvotes: 3

Rogue
Rogue

Reputation: 11483

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

Upvotes: 1

Related Questions