File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Performance and the fly likes Are ArrayList really slower than LinkedList? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Are ArrayList really slower than LinkedList?" Watch "Are ArrayList really slower than LinkedList?" New topic
Author

Are ArrayList really slower than LinkedList?

Barkat Mardhani
Ranch Hand

Joined: Aug 05, 2002
Posts: 787
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

Joined: Jan 30, 2000
Posts: 18671
I'm going to move this to the Performance forum since that's what it's about. Hopefully K&B will follow...


"I'm not back." - Bill Harding, Twister
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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

Joined: Aug 05, 2002
Posts: 787
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
 
 
subject: Are ArrayList really slower than LinkedList?
 
Similar Threads
Problem While Removing Element From List
get elapsed time....
ArrayList vs LinkedList?
LinkedList problem
Difference between ArrayList and LinkedList?