1. Senior Member
Join Date
Jan 2012
Posts
151
Rep Power
9

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

2. Senior Member
Join Date
Oct 2010
Location
Germany
Posts
785
Rep Power
12

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

3. ## 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

4. Senior Member
Join Date
Jan 2012
Posts
151
Rep Power
9

## Re: efficiency question

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

5. Member
Join Date
Sep 2010
Posts
84
Rep Power
0

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

6. Senior Member
Join Date
Jan 2012
Posts
151
Rep Power
9

## 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);

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?

7. Senior Member
Join Date
Apr 2012
Location
New York State of Confusion, USA
Posts
137
Blog Entries
1
Rep Power
0

## Re: efficiency question

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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•