0

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("\nThe element Orange is removed");
            break;
         }
      }
Stefan Zobel
  • 3,182
  • 7
  • 28
  • 38
DerWolferl
  • 71
  • 7
  • 1
    There is no benefit in this code. Just use `if (aList.remove("Orange")) System.out.println(...)`. – Andy Turner Jul 17 '19 at 20:35
  • @AndyTurner: Sometimes, you can't do that. And by "sometimes" I mean "very often if you're working with classes you don't control and haven't implemented `equals` *or* `hashCode`." – Makoto Jul 17 '19 at 20:56
  • If you’re curious how your iterator compares to the internal one, check out the OpenJDK source for eg. `ArrayList`: https://github.com/openjdk/jdk/blob/fb6ce41689e11cacafc5de494188798c6b81bb99/src/java.base/share/classes/java/util/ArrayList.java#L598-L641 – MTCoster Jul 17 '19 at 20:58
  • In case of streams you can start parallel processing with just one command like `parallelStream()` or `stream().parallel()` – Ivan Jul 17 '19 at 21:00

2 Answers2

5

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(n²) 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.

Holger
  • 285,553
  • 42
  • 434
  • 765
0

So I'm going to stop you right here - your terminology doesn't make any sense. What you were probably trying to get at was the concept of an inner loop, which is effectively iterating inside of an iteration, much like the dials of an analog watch.

Your code only has one loop. It's the while loop, and that's it. This makes that part of your question...effectively moot. You can iterate over a collection or collections of collections (of collections...) as many times as you want, or need.

Otherwise, this is the correct way to delete elements from a collection while iterating it; any other approach would get you a ConcurrentModificationException. If you wanted to call that a performance benefit, then you'd have the benefit of not throwing an exception when you wanted to remove elements in this fashion.

Makoto
  • 104,088
  • 27
  • 192
  • 230
  • I copied the code and just noticed I didn't copy the whole important part. But the point of my question was, what the benefits of internal iterations vs external iterations are and if it's generally possible to delete elements of a collection while iterating over it with an internal stream. The code example maybe was just a bit confusing. – DerWolferl Jul 18 '19 at 12:02