aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes ArrayList vs LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "ArrayList vs LinkedList" Watch "ArrayList vs LinkedList" New topic
Author

ArrayList vs LinkedList

Vad Fogel
Ranch Hand

Joined: Aug 25, 2003
Posts: 504
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"?
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
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.


Associate Instructor - Hofstra University
Amazon Top 750 reviewer - Blog - Unresolved References - Book Review Blog
Vad Fogel
Ranch Hand

Joined: Aug 25, 2003
Posts: 504
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 ]
Jim Yingst
Wanderer
Sheriff

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


"I'm not back." - Bill Harding, Twister
Vad Fogel
Ranch Hand

Joined: Aug 25, 2003
Posts: 504
Thank you Jim and Thomas for your clarifications!
Thomas Paul
mister krabs
Ranch Hand

Joined: May 05, 2000
Posts: 13974
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: ArrayList vs LinkedList