Win a copy of Java Challengers this week in the Java in General forum!
  • 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
  • Paul Clapham
  • Ron McLeod
  • paul wheaton
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Liutauras Vilda
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Piet Souris
Bartenders:
  • salvin francis
  • Mikalai Zaikin
  • Himai Minh

Are ArrayList really slower than LinkedList?

 
Ranch Hand
Posts: 787
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Kathy and Berts,
Quote from your book:

LinkedList A LinkedList List is ordered by index position, like ArrayList, except
that the elements are doubly-linked to one another. This linkage gives you new methods
(beyond what you get from the List interface) for adding and removing from the
beginning or end, which makes it an easy choice for implementing a stack or queue.
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.


I am not finding that with following code. Times are noted in the comments.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I'm going to move this to the Performance forum since that's what it's about. Hopefully K&B will follow...
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For inserts and deletes: ArrayList and LinkedList are fairly comparable at the end of the List. (I think ArrayList comes out ahead, but it's generally not a big difference.) If you try insert or delete at the beginning of the List, LinkedList will be much better. The performance of ArrayList gets worse the farther you are from the end when you insert or delete; the performance of LinkedList gets worse the farther you are from the beginning or the end. So neither one is so great when you're in the middle. However, if you are traversing the list with a ListIterator, and you've already got the ListIterator at the position you need, then using add() or remove() on the ListIterator is very vast for a LinkedList, and poor for ArrayList. So if you want to do something like this:

Then LinkedList will definitely do better. LinkedList is lousy at random access, but at the beginning or end, or through an iterator already in position, it's fast. ArrayList is great at random access, but lousy at inserts/deletes away from the end. For many applications, you will observe a combination of these effects, and it's useful to just try both types of List to see which works better.
 
Barkat Mardhani
Ranch Hand
Posts: 787
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Jim. I was trying to point out that statement K&B was a blanket statement. It needed the details you pointed out.
Thnks
Barkat
reply
    Bookmark Topic Watch Topic
  • New Topic