Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

LinkedHashMap and LinkedList, iteration time doubt

 
Yeray Santana Borges
Ranch Hand
Posts: 46
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
wei ma
Ranch Hand
Posts: 39
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 952
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
M Kothawade
Greenhorn
Posts: 9
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic