Iterating through collection

In my opinion, iterating through a collection is very basic and simple thing because it appears in any developer’s code everyday (of course in the languages support collection).

It’s normally my simplest question to start the interview to warmup and make the candidate more confident. But I’m wrong. I’m so surprised that 90% of our candidates, who have been (senior) developers for 2-3 years, cannot give the right answer:

Let say I have a collection LinkedList<int> list. What are differences between 2 types of iterating through list:

for (int i = 0; i < list.length(); i++) {
    int item = list.get(i);
    // do something here...
}

and

for (int item : list) {
    // do something here...
}

Most of answer I got is “we can have the index by #1 code that we cannot have in #2 code. The performance are the same.”. But it’s incorrect, #1 is really bad code in performance wise.

The performance are the same in the index-based collection, like array or ArrayList. But #1 code is very slow in other collection like LinkedList. The reason is for getting the item at index i (by calling get(i) method), LinkedList needs to iterate from the first item with the counter set to 0, increase it in each step and stop when the counter reach to i. So while the notation of #1 code is O(N²), the notation of #2 code is O(N).

#2 code actually works as

for (Iterator iterator = list.iterator(); iterator.hasNext();) {
    int item = (int)iterator.next();
}

#3 code is exactly the way #2 code works before Java introduced for each syntax.

The best solution is always use #2 code for iterating through any collection. If you are worry about the index, another code would be:

int index = 0;
for (int item : list) {
    index++;
    // do something here...
}

Java is just a used language here but I believe this way works in any language today. Whatever the technology you are chasing, let start from the basic things, language and data structure.