• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Are ArrayList really slower than LinkedList?

 
Barkat Mardhani
Ranch Hand
Posts: 787
  • Mark post as helpful
  • send pies
  • 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.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • 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
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • 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
  • 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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic