efficiency question

[stuckonjava]

When I run a method that counts amount of even numbers over 200,000 numbers on an arraylist and linkedlist, the array list completes in less than a second while the linked list takes almost half a minute. Can someone explain why the arraylist performs it so much more faster.

[eRaaaa]

Give us a whole example. The numbers are already in the list? You only read from the list? If, in which way?
Do you understand the differents between arraylist and linkedlist implementations?

[JosAH]

Finding element #n in an ArrayList takes one single operation while it takes n operations for a LinkedList (it's all in the API documentation).

kind regards,

Jos

[stuckonjava]

Finding element #n in an ArrayList takes one single operation while it takes n operations for a LinkedList (it's all in the API documentation).

kind regards,

Jos

Could you explain this quickly please? I understand both of the ADTs but I don't get how the arraylist does it quicker

[Danieldcc]

newbie here; I think an array can reference by a[i] so you directly go to that element that is required....with a linked list there is no referencing the i'th element so every time you do an operation it starts from the beginning of the linked list and traverses through the list until it finds the element that it needs, that's why takes much longer.............so if you have 100k elements, linked list has to go through each one to reach the element that you might want. that's what i assume

[stuckonjava]

// count even numbers in a sequence of integers public static int countEven(List<Integer> seq) {
int c = 0; for (int i = 0; i < seq.size(); i++) {
if ( seq.get(i) % 2 == 0 ) { c++; }
} return c;

//fill up the array and linkelist seqArr is the arraylist and seqLL is the linkedlist.
int n = Integer.parseInt(args[0]);
for (int i = 0; i < 400000; i++) {
int n = (int) (Math.random() * 100);
seqArr.add(n);
seqLL.add(n);

Than I use the method countEven on both of them.

Hopefully this clears it up. Why does the array come back with the answer quicker?

[jlczuk]

According to the API documentation for LinkedList, it implements a doubly linked list. When you use indices to access entries, the implementation starts at the head or tail of the list, whichever is closer, and must traverse the list to get to the desired index. That traversal is what you are experiencing as an extended elapsed time to completion compared to the direct access that the ArrayList implementation affords you.