# efficiency question

• 04-24-2012, 07:57 PM
stuckonjava
efficiency question
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.
• 04-24-2012, 08:10 PM
eRaaaa
Re: efficiency question
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?
• 04-24-2012, 08:48 PM
JosAH
Re: efficiency question
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
• 04-25-2012, 12:07 AM
stuckonjava
Re: efficiency question
Quote:

Originally Posted by 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

Could you explain this quickly please? I understand both of the ADTs but I don't get how the arraylist does it quicker
• 04-25-2012, 12:15 AM
Danieldcc
Re: efficiency question
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
• 04-25-2012, 12:47 AM
stuckonjava
Re: efficiency question
// 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);