Year ago, I had a post about iterating through collection. Today my colleague’s question gave me the idea about an example of using collection right. Let’s say we have a collection like NSArray that contains multiple NSString objects, we want to print them in lines includes the line number.

Easy problem, right? Let’s see we have some solutions:

What’s a best way? I can say #2 > #3 | #1.

About #3, you can refer to my post to know why we should use iterator instead of index while going through collection. Of course they perform same with NSArray but using iterator help us more easily use another collection type later. So #1 and #2 are usually better than #3. Why is #2 better than #1? The issue is:

#1 is O(n) while #2 is O(1). We can see #1 is more readable (a bit easier to understand than #2) but #2 has better performance.

You could see #1 is worser in some way. In case of duplicated strings in lines, you may also get wrong result (index is the first found): http://stackoverflow.com/questions/3167849/indexofobject-vs-indexofobjectidenticalto 

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:

and

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(N2), the notation of #2 code is O(N).

#2 code actually works as

#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:

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.

473 total views, 1 views today