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"?
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.
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 ]
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
Joined: Aug 25, 2003
Thank you Jim and Thomas for your clarifications!
Joined: May 05, 2000
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.