Iterator vs get(index) method

Iterator vs get(index) method

We can traverse list using for loop or an Iterator. Sometimes iterator perform traversing faster than for loop for example, linked list is a classic example, Linked list class has get(index) method but it is slow because linked list is a sequential data structure and here is the implementation of get(index) method (taken from  java.util.LinkedList class)

As we can see to get the element at particular index java needs to put some effort, it has to reach up to that index to get the element at that particular index

If list is accessed frequently then you will see the difference in performance while using get(index) method of linked list as compared to traversing list using iterator.

Let’s take a look at the following example:-

public class Performance {

                public static void main(String[] args) {

                                int count = 100000;

                                LinkedList<Integer> linkedLst = new LinkedList<Integer>();

                                ArrayList<Integer> arrayLst = new ArrayList<Integer>();

                                for (int i = 0; i != count; i++) {

                                                int x = (int) Math.random();

                                                linkedLst.add(x);

                                                arrayLst.add(x);

                                }

                                long t = System.currentTimeMillis();

                                for (int i = 0; i != count; i++) {

                                                linkedLst.get(i);

                                }

                                t = System.currentTimeMillis() - t;

                                System.out.println("Time taken by Linked List get(index) " + t + "(ms)");

                                t = System.currentTimeMillis();

                                for (Iterator<Integer> itr = linkedLst.iterator(); itr.hasNext();) {

                                                itr.next();

                                }

                                t = System.currentTimeMillis() - t;

                                System.out.println("Time taken by Linked List Iterator " + t + "(ms)");

                                t = System.currentTimeMillis();

                                for (int i = 0; i != count; i++) {

                                                arrayLst.get(i);

                                }

                                t = System.currentTimeMillis() - t;

                                System.out.println("Time taken by Array List get(index) " + t + "(ms)");

                                t = System.currentTimeMillis();

                                for (Iterator<Integer> itr = arrayLst.iterator(); itr.hasNext();) {

                                                itr.next();

                                }

                                t = System.currentTimeMillis() - t;

                                System.out.println("Time taken by Array List Iterator " + t + "(ms)");

                }

}

And the output of the above program is (on my machine)

Time taken by Linked List get(index) 3412(ms)

Time taken by Linked List Iterator 9(ms)

Time taken by Array List get(index) 3(ms)

Time taken by Array List Iterator 7(ms)

You can see the difference in performance therefore if you want to traverse list then choose option wisely J.

And in many cases you don’t know whether you want a linked list or an array list or some other list implementation in that case using iterator to traverse a list is a more reliable choice because iterator gives fairly good performance in case of array list (although not fastest) and in case of traversing linked list it gives much comparable results then for loop and it protects from the extremely slow performance you would get if you mistakenly used a get(index) on a linked list.