• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

LinkedList - Kathy Sierra

 
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Kathy Sierra says use ArrayList rather than LinkedList if you need faster iteration.

Examlab says use LinkedList.

Which one is true ???
 
Ranch Hand
Posts: 196
Android Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
i suppose that k&b book's statement is true......


ArrayList is faster during iteration when compared to LinkedList.....

 
Ranch Hand
Posts: 1183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It depends how you loop through it.

First, ArrayList is using arrays which are index-based, so it's complexity for obtaining objects is always 1.

LinkedList is implemented using chain of connected elements. So if you want to obtain element 500, it has to traverse from element 1 to 500 (complexity is n). That is why ArrayList ist faster for obtaining objects than LinkedList.

Now, if you use the ListIterator, LinkedList might keep track of what the next element is and therefore be just as fast, not sure though.
 
Sebastian Janisch
Ranch Hand
Posts: 1183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I glanced into the implementation of LinkedList. The Iterator indeed keeps track of the following element, which should make the iteration just as fast compared to ArrayList.
 
Ranch Hand
Posts: 49
1
Netbeans IDE Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I disagree. LinkedList may be just as fast when looping through the list but ArrayList will still be faster when getting an arbitrary index. Say you need to get The object at index=723. With ArrayList, since it uses arrays, it will be just as fast as a normal array (array[723]) to get the object. With Linked list the implementation will have to loop through elements 0 to 723 to get the right object. Clearly ArrayList is much faster because it doesn't have to loop at all.
 
Sebastian Janisch
Ranch Hand
Posts: 1183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Uhm, that's exactly what I said in my previous posts.
reply
    Bookmark Topic Watch Topic
  • New Topic