• 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

ArrayList vs LinkedList

 
Ranch Hand
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
K&B states that ArrayList is better suited for random access and iteration when insert/delete is less likely to occur:


Choose this [ArrayList] over a LinkedList when you need fast iteration but aren�t as likely to be doing a
lot of insertion and deletion.


LinkedList is best at fast insert/delete operations. However, Thomas' article on performance at The List Interface shows that a LinkedList is about 1.4 times faster doing plain iterations than an ArrayList. Why not choose LinkedList over ArrayList for all purposes but random access? And how to answer a potential exam question "what List implementation class is best for fast iteration"?
 
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I just ran some more tests using JDK 1.4.2 and I can find little difference in time between iterating between a LinkedList and an ArrayList. Iterating through 1,000,000 entries took about 10 ms longer in the ArrayList.
The random access times between the two still heavily leans in favor of the ArrayList.
 
Vad Fogel
Ranch Hand
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
J. Bloch Collection Implementations


The two general purpose List implementations are ArrayList and LinkedList. Most of the time, you'll probably use ArrayList. It offers constant time positional access, and it's just plain fast, because it does not have to allocate a node object for each element in the List, and it can take advantage of the native method System.arraycopy when it has to move multiple elements at once.


Joshua doesn't compare iteration speed, but he explicitly mentions that ArrayList is a preferrable List implementation in most cases where inserts/deletes are not there. Can we assume it also applies to plain iteration?
[ November 02, 2003: Message edited by: Vad Fogel ]
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And how to answer a potential exam question "what List implementation class is best for fast iteration"?
Don't worry about it. Differences here are just not big enough to warrant a test question like this. Also since if you really care about fast access, you wouldn't use an Iterator on an ArrayList, you'd use a for loop with an nidexed get(), and this will be faster. But again, not by that much, and it's just not worthwhile to worry about all the poorly phrased test questions you might imagine you'll see. The important differences between ArrayList and Linked List are for random access (ArrayList is better) and for insert/delete from the beginning or from an iterator (LinkedList is better). Differences in other areas are relatively trivial. If you understand these, you're set; move on to something else.
 
Vad Fogel
Ranch Hand
Posts: 504
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you Jim and Thomas for your clarifications!
 
Thomas Paul
mister krabs
Posts: 13974
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
One important thing to keep in mind is that if you are iterating through a List always use an iterator. Never use a for loop. Why not? If you use a for loop on an ArrayList and then later you need to change to a LinkedList you will see performance go right in the toilet. Iterators perform well for both.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic