*
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


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Iterator for ArrayList and LinkedList" Watch "Iterator for ArrayList and LinkedList" New topic
Author

Iterator for ArrayList and LinkedList

Naresh Chaurasia
Ranch Hand

Joined: May 18, 2005
Posts: 356
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: 443
    
    1

Hello,

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.

Cheers,
Raj.
Deepak Bala
Bartender

Joined: Feb 24, 2006
Posts: 6661
    
    5

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 Entry.next 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
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Iterator for ArrayList and LinkedList