aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes LinkedHashMap and LinkedList, iteration time doubt 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 "LinkedHashMap and LinkedList, iteration time doubt" Watch "LinkedHashMap and LinkedList, iteration time doubt" New topic
Author

LinkedHashMap and LinkedList, iteration time doubt

Yeray Santana Borges
Ranch Hand

Joined: Mar 02, 2008
Posts: 46
After look in K&B book, i have yet doubt about this classes:

LinkedHashMap --> fast iteration but slow insert/delete (comparing with HashMap)
LinkedList --> fast insert/delete but slow iteration (comparing with ArrayList)

Is it true?

Thanks


SCJP 6 - SCWCD 5 - SCBCD 5
wei ma
Ranch Hand

Joined: Jul 18, 2001
Posts: 39
I believe this is deeper than what SCJP requires. But yes, I agree with you. The underline implementation of ArrayList is array, so inserting element would be a pain when the original array is full and you have to expand the size. However, retrieving element from array is fast, all you need to do is
while in linkedList your have to do:



Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952
Yes it is true.

Iteration : ArrayList has indexed elements, so it can jump directly at last element at anytime in O(1) time, while LinkedList will take O(N) time. So faster iteration than LinkedList.
LinkedHashMap extends HashMap plus uses doubly linked list so it has faster iteration than HashMap.

Insertion/Deletion: LinkedHashMap has to maintain insertion order so it is slower than HashMap in insertion/deletion.
ArrayList has to move elements upside or downside if you insert or delete that will require O(N) time, while LinkedList just has to change its references to its elements that takes only O(1) time. So linkedlist is faster here.


SCJP 6
M Kothawade
Greenhorn

Joined: Dec 29, 2008
Posts: 9
Kindly note that he mentioned 'iteration' and not 'random access' for linked list.
I feel iteration "might be" slower in linkedlist compared to arrayList but if it is slower it has to be slightly slower and not considerably slower.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: LinkedHashMap and LinkedList, iteration time doubt