java - Benefits of internal iterations

Question

I just wanted to know, what the real benefits of Internal vs External Iterations are and why it is better to use internal operations (that's what I heard at least). Is it also possible to delete elements of a collection while internally iterating over the collection? Like in the code example:

I know that the code readability of internal iterations is better, but are there some other benefits like performance improvements?

//List with Strings of Fruit-Names
      Iterator i = aList.iterator();
      String str = "";
      while (i.hasNext()) {
         str = (String) i.next();
         if (str.equals("Orange")) {
            i.remove();
            System.out.println("
The element Orange is removed");
            break;
         }
      }

Answer 1

Your condition is somewhat simplistic, as you could simply use aList.remove("Orange") resp. aList.removeAll(Collections.singleton("Orange")) instead, but there is an alternative with internal iteration which also works with more complex conditions, aList.removeIf(str -> str.equals("Orange")).

In case of ArrayList, this will immediately show the advantage of internal iteration: in case of calling remove() on an Iterator, the ArrayList has no control over the loop, hence doesn’t know when you exit it resp. abandon the Iterator. You can access the list through the List interface at any time, reading and continue iterating or writing and not iterating further.

So every time you invoke remove(), the list has to be brought into a consistent state, i.e. all subsequent elements have to be copied at the right place when removing an element. This gives iterating and removing from an ArrayList a worst case of O(n2) time complexity.

In contrast, the removeIf method only has to provide a completed state of the List when the method returns. Hence, it may postpone copying elements to the point when the final position is known, which makes it an O(n) operation. So, for large lists, there’s a significant performance advantage.

Generally, methods with internal iterations provide the possibility of being implemented optimized for the particular internal data structure, while never being worse than the external loop, as the iterator based loop is the fallback of these methods anyway.