File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Iterator for ArrayList and LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Iterator for ArrayList and LinkedList" Watch "Iterator for ArrayList and LinkedList" New topic

Iterator for ArrayList and LinkedList

Naresh Chaurasia
Ranch Hand

Joined: May 18, 2005
Posts: 361
While reading Generics and Collection, chapter7 from kathy sierra, I came across the following statement.

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.

Does it mean that if i define an iterator on ArrayList and LinkedList and traverse the List using the iterator, then traversal will be faster in case of ArrayList. If "Yes", then why is it that ArrayList is faster compared to LinkedList.

Please advice

SCJP 1.4, SCWCD1.4, OCA(1Z0-007)
Rajkamal Pillai
Ranch Hand

Joined: Mar 02, 2005
Posts: 445


LinkedList: Is stored in memory as a contiguous array. So the new elements added to the collection can be physically stored anywhere in memory with a pointer from the previous element in the data structure pointing to the next. This is why the iteration *could be* comparatively slower.

ArrayList: Is stored in memory as blocks. If there is no more free space available to ad another element then the whole of the collection gets copied to a new location. This is why insertion/deletion *could be* comparatively slower.

The faster/slower comparison, in IMHO, is relative to the operation being performed.

Deepak Bala

Joined: Feb 24, 2006
Posts: 6662

LinkedList: Is stored in memory as a contiguous array

No its not. The elements are represented by an internal Entry class (very much like Map.Entry). Arrays are not involved.

ArrayList: Is stored in memory as blocks.

The internal data structure is an array, if that is what you meant.

Traversing through all the elements will always take O(N) time. Be it an ArrayList or a LinkedList.

Obtaining any particular element at a given index is another question. With an array backed ArrayList, it is as simple as returning array[index]. With the LinkedList, one has to traverse through the members using until the element at the given index is reached. The worst case is O(N) for LinkedList, while for ArrayList the retrieval operation is always O(1).

As for insertion, LinkedList can grow its structure without copying over elements, while arrays do not have this luxury.

SCJP 6 articles - SCJP 5/6 mock exams - More SCJP Mocks
I agree. Here's the link:
subject: Iterator for ArrayList and LinkedList
It's not a secret anymore!