When iterating through a LinkedList, get(i) is an O(N) operation. It makes sense then that we use an Iterator object to traverse the list. But with an ArrayList, get(i) is O(1). So, in that case am I correct in saying that when using an ArrayList, it doesn't make a difference whether we use a c-style loop or an Iterator object?
Add a comment
|
3 Answers
You are correct. You should avoid loops like this
for (int i = 0; i < linkedList.size(); i++) {
... linkedList.get(i) ...
}
for a LinkedList because get(i) is O(n) so the whole process becomes O(n^2).
For an ArrayList it does not matter as both iterator.next() and get(i) are O(1).
However, you usually do not need to explicitly use an Iterator object even for a LinkedList because a foreach loop for (Object object : linkedList) uses an Iterator in the background anyway.
Iterators only need to be used explicitly in relatively rare situations (e.g. filtering a List or traversing two LinkedLists in parallel).
Comments
Using an Iterator is less error-prone when removing elements, compared to a while loop, because you don't have to adjust some position value (i, cursor, whatever you call it) when removing. A for loop is already using the iterator, as @Vivin Paliath explained, and doesn't work with removals (removals will cause ConcurrentModificationExceptions).
Comments
Yes, it would be O(n) in both cases for ArrayList. If you're using the iterator to look up an element, in the worst case you would have to check every element. In the average case you would have to check half. Hence it's still O(n).
Also, the for syntax for iterating over a list is just syntactic sugar for invoking the iterator. If you look at the compiled bytecode, you will see that it invokes the iterator for the list.
For example, the following code:
import java.util.*;
public class IterTest {
public static void main() {
List<String> l = new ArrayList<>();
for(String s : l) {
System.out.println(s);
}
}
}
Has the following bytecode:
Compiled from "IterTest.java"
public class IterTest {
public IterTest();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main();
Code:
0: new #2 // class java/util/ArrayList
3: dup
4: invokespecial #3 // Method java/util/ArrayList."<init>":()V
7: astore_0
8: aload_0
9: invokeinterface #4, 1 // InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
14: astore_1
15: aload_1
16: invokeinterface #5, 1 // InterfaceMethod java/util/Iterator.hasNext:()Z
21: ifeq 44
24: aload_1
25: invokeinterface #6, 1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
30: checkcast #7 // class java/lang/String
33: astore_2
34: getstatic #8 // Field java/lang/System.out:Ljava/io/PrintStream;
37: aload_2
38: invokevirtual #9 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
41: goto 15
44: return
You can see that it's using the iterator to loop over the list.
UPDATE
In response to your comment:
Your for loop with an index will have the same performance as the explicit iterator and the for iterator-style loop if you are using an ArrayList.
However, using the for with an index with a LinkedList will be strictly worse (on average) than the ArrayList, since for each index, you are performing an O(n) lookup. Hence, your total performance actually ends up being O(n2).
2 Comments
orrymr
What if I loop like this: for(int i = 0; i < myList.size(); i++){//do stuff which involves myList.get(i)} Surely that's also just O(n), since myList.get(i) is constant time? In which case it doesn't matter if I use an Iterator or not?
Vivin Paliath
@orrymr Yes, that is
O(n) as well. Technically it doesn't matter since the performance for traversing the ArrayList is the same in all cases. I prefer using the for iterator-syntax since it is much more readable. But it may be that in some cases, it is more idiomatic to use the iterator or a for loop with an index.