Question regarding LinkedList in Java

Question

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 ?

Answer 1

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

https://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.

• Chuck Stephanski: 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.
• jmq: 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)

Answer 2

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.

• barjak: you are answering the question "why the indexed access is slower", and not "why the iteration is slower".