Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

When I was reading a book for SCJP, I came across the following paragraph.

A LinkedList is ordered by index position, like ArrayList, except that the elements are doubly-linked to one another. This linkage gives you new methods (beyond what you get from the List interface) for adding and removing from the beginning or end, which makes it an easy choice for implementing a stack or queue. Keep in mind that a LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion..

What makes a LinkedList to iterate more slowly than an ArrayList ?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Here is an answer from stackoverflow that explains it pretty well:

http://stackoverflow.com/questions/716597/array-or-list-in-java-which-is-faster

Basically, the ArrayList is contiguous where the LinkedList is not. Incrementing to the next location in memory with the ArrayList is considered faster than jumping to the next location via a reference in LinkedList. Also, maintenance of the LinkedList would incur overhead to maintain two sets of references for a doubly linked list.

share|improve this answer
1  
I read the SO post and a couple of posters say they doubt java keeps ArrayList members in contiguous memory, especially for large arrays. The OP doesn't cite the book - it may well be wrong. –  Chuck Stephanski Mar 23 '11 at 7:15
2  
I was looking through the ArrayList java code last night and saw that the ArrayList is instantiated as an array internally. I couldn't find anywhere in the java spec that would guarantee that a normal array would be contiguous though, so yeah, that may be the case (so I may need to rescind that answer) –  jmq Mar 23 '11 at 14:07

I haven't looked at these classes in Java but typically an array will be faster than a linked list because in a linked list the list is made up of a series of nodes which each of a "link" to the next node in the sequence. So when you ask for the 10th element it has to cycle through 10 elements to pull the one you want. In an array (unless I'm mistaken) calling for an element takes you straight to that element.

share|improve this answer
    
you are answering the question "why the indexed access is slower", and not "why the iteration is slower". –  barjak Mar 23 '11 at 17:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.