CODEWITHSUNDEEP
javaalgorithmiteratorperformance
TMGunter
TMGunter

Reputation: 137

Seeking further understanding on Iterators in java

If I am using a for loop (the standard for loop, not an enhanced for statement), I fail to see how an iterator increases efficiency when searching through a collection. If I have a statement such as:

(Assuming that aList is a List of generic objects, type E, nextElement refers to the next element within the list)

for (int index = 0; index < aList.size(); index++){
E nextElement = aList.get(index);
// do something with nextElement...
}

and I have the get method that looks something like:

Node<E> nodeRef = head;
for (int i = 0; i < index; i++){
    nodeRef = nodeRef.next;
    // possible other code
}

this would essentially be searching through the List, one element at a time. However, if I use an iterator, will it not be doing the same operation? I know an iterator is supposed to be O(1) speed, but wouldn't it be O(n) if it has to search through the entire list anyway?

Upvotes: 5

Views: 521

Answers (6)

Wivani
Wivani

Reputation: 2046

Remember that it's also a Design Pattern.

"The Iterator Pattern allows traversal of the elements of an aggregate without exposing the underlying implementation. It also places the task of traversal on the iterator object, not on the aggregate, which simplifies the aggregate interface and implementation, and places the responsibility where it should be." (From: Head First Design Pattern)

It's about encapsulation and also the 'single responsibility' principle.

Cheers, Wim

Upvotes: 1

Matthew
Matthew

Reputation: 13332

Like Jon said, iterators have nothing to do with efficiency they just abstract the concept of being able to iterate over a collection. So you are right, if you are just searching through a list there is no real benefit to an iterator over a for loop, but in some cases iterators provide convenient ways for doing things that would be difficult with a simple for loop. For example:

while(itr.hasNext()) {
    if(itr.next().equals(somethingBad);
         itr.remove();
}

In other cases iterators provide a way to traverse the elements of a collection, that you can not fetch by index (eg a hashset). In this case a for loop is not an option.

Upvotes: 1

Michael Yoon
Michael Yoon

Reputation: 1606

Iterators are not about increasing efficiency, they're about abstraction in the object-oriented sense. Implementation-wise, the iterator is doing something similar to what you're doing, going through your collection one element at a time, at least if the collection is index-based. It's supposed to be O(1) when retrieving the next element, not the entire list. Iterators help mask what collection is underneath as well, it could be a linked list or a set, etc, but you don't have to know.

Also, notice how connected your for loop is to your specific logic that you want to do on each element, while with an iterator you can abstract out the looping logic from whatever action you want to do.

Upvotes: 2

Roland Illig
Roland Illig

Reputation: 41617

You are using a linked list here. Iterating over that list without an iterator takes O(n^2) steps, where n is the size of the list. O(n) for iterating over the list and O(n) each time for finding the next element.

The iterator, on the other hand, remembers the node it has visited the last time, and therefore needs only O(1) to find the next element. So eventually the complexity is O(n), which is faster.

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500155

It's not primarily about efficiency, IMO. It's about abstraction. Using an index ties you to collections which can retrieve an item for a given index efficiently (so it won't work well with a linked list, say)... and it doesn't express what you're trying to do, which is iterate over the list.

With an iterator, you can express the idea of iterating over a sequence of items whether that sequence can easily be indexed or not, whether the size is known in advance or not, and even in cases where it's effectively infinite.

Your second case is still written using a for loop which increments an index, which isn't the idiomatic way of thinking about it - it should simply be testing whether or not it's reached the end. For example, it might be:

for (Node<E> nodeRef = head; nodeRef != null; nodeRef = nodeRef.next)
{
}

Now we have the right abstraction: the loop expresses where we start (the head), when we stop (when there are no more elements) and how we go from one element to the next (using the next field). This expresses the idea of iterating more effectively than "I've got a counter starting at 0, and I'm going to ask for the value at the particular counter on each iteration until the value of the counter is greater than some value which happens to be the length of the list."

We're fairly used to the latter way of expressing things, but it doesn't really say what we mean nearly as may as the iterator approach.

Upvotes: 11

Ray Toal
Ray Toal

Reputation: 88378

I think the question you are asking refers to the efficiency of iterators vs. a for-loop using an explicit get on the collection object.

If you write code with a naive version of get, and you iterate through your list using it, then it takes you

  • one step to "get" the first element
  • two steps to "get" the second
  • three steps to get the third
  • ...
  • n steps to get the last

for a total of n(n-1)/2 operations, which is O(n^2).

But if you used an iterator which internally kept track of the next element (i.e. one step to advance), then iterating the whole list is O(n), a big improvement.

Upvotes: 1

Related Questions