LinkedList: remove an object

Question

Is this a valid way to find and remove item from a LinkedList in Java using a for each loop, is it possible that inconsistency may arise:

for(ObjectType ob : obList) {
  if(ob.getId() == id) {
    obList.remove(ob);
    break;
   }
}

Answer 1

Edit: Indeed, it will not fail thanks to the break. See polygenelubricant's answer for details.

However, this is dangerous way to do. To concurrently iterate and modify a collection in Java, you must use the "ListIterator" object, and use the iterator's own "add()" and "remove()" methods, and not use the ones on the collection.

You can check the java doc for the "java.util.Iterator" and "java.util.ListIterator" classes

Answer 2

Others have mentioned the valid point that normally this is not how you remove an object from a collection. HOWEVER, in this case it's fine since you break out of the loop once you remove.

If you want to keep iterating after a remove, though, you need to use an iterator. Otherwise you'll get a ConcurrentModificationException, or in the more general case, undefined behavior.

So yes, if you break out of the foreach after you remove, you'll be fine.

---

To those who's saying that this will fail because you can't modify a collection in a foreach -- this is true only if you want to keep iterating. That's not the case here, so this shortcut is fine.

A ConcurrentModificationException is checked and thrown by the iterator. Here, after the remove (which qualifies as concurrent modification), you break out of the loop. The iterator doesn't even get a chance to detect it.

It may be best if you add a comment on the break, why it's absolutely necessary, etc, because if this code is later modified to continue iterating after a remove, it will fail.

I would treat this idiom similar to goto (or rather, labeled break/continue): it may seem wrong at first, but when used wisely, it makes for a cleaner code.

Answer 3

Try something like this:

Iterator<ObjectType> iter = obList.iterator();
while (iter.hasNext()) {
  ObjectType ob = iter.next();
  if(ob.getId() == id) {
    iter.remove();
    break;
  }
}

That's one of the last places where an Iterator cannot be replaced by a foreach loop.

Answer 4

A CopyOnWriteArrayList might be what you're looking for. When mutative operations are performed, a copy of the underlying array is made. This allows modification of list elements while inside a for-each loop. Remember though that this is not a linked list and can be quite inefficient.

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {

    public static void main(String[] args) {
        List<String> myList = new CopyOnWriteArrayList<String>();

        myList.add("a");
        myList.add("b");
        myList.add("c");

        // Will print [a, b, c]
        System.out.println(myList);

        for (String element : myList) {
            if (element.equals("a")) {
                myList.remove(element);
            }
        }

        // Will print [a, c]
        System.out.println(myList);
    }

}

Answer 5

You should use iterator.remove():

Removes from the underlying collection the last element returned by the iterator (optional operation). This method can be called only once per call to next. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

Answer 6

To avoid a ConcurrentModifiationException, you could do:

final Iterator<ObjectType> i = obList.iterator();
while (i.hasNext()) {
    if (i.next().getId() == id) {
        i.remove();
    }
}

or

for (int i = 0; i < obList.size(); i++) {
    if (obList[i].getId() == id) {
        obList.remove(i);
    }
}

I would prefer the first. Handling indices is more errorprone and the iterator may be implemented efficiently. And the first suggestion works with Iterable while the second requires a List.

Answer 7

It is best to use an iterator and use it's remove method when searching for an object by iterating over a collection in order to remove it. This is because

1. The collection could be, for example, a linked list (and in your case it is) whose remove method means searching for the object all over again, which search could have O(n) complexity.
2. You can't continue iteration after the remove unless you use the iterator's remove method. Right now you are removing the first occurrence - in future you might need to remove all matching occurrences, in which case you then have to rewrite the loop.

I recommend, on principle, foregoing the enhanced for and using something like this instead:

for(Iterator<ObjectType> it=obList.iterator(); it.hasNext(); ) {
    if(it.next().getId()==id) { 
        it.remove(); 
        break;
        }
    } 

That way you are not making assumptions about the underlying list that could change in the future.

---

Compare the code to remove the last entry called by the iterator remove (formatting Sun's):

private E remove(Entry<E> e) {
    if (e == header)
        throw new NoSuchElementException();

    E result = e.element;
    e.previous.next = e.next;
    e.next.previous = e.previous;
    e.next = e.previous = null;
    e.element = null;
    size--;
    modCount++;
    return result;
}

against what remove(Object) must do:

public boolean remove(Object o) {
    if (o==null) {
        for (Entry<E> e = header.next; e != header; e = e.next) {
            if (e.element==null) {
                remove(e);
                return true;
            }
        }
    } else {
        for (Entry<E> e = header.next; e != header; e = e.next) {
            if (o.equals(e.element)) {
                remove(e);
                return true;
            }
        }
    }
    return false;
}