ArrayList access speed

[Mark Herschberg]

Taken from http://java.sun.com/docs/books/tutorial/collections/implementations/general.html:
Most of the time, you'll probably use ArrayList. It offers constant time positional access

Is this right? ArrayList offers constant time positional access? I take that to mean that the get(int) method is constant time. But in the javadoc it says

Taken from http://java.sun.com/products/jdk/1.2/docs/api/java/util/ArrayList.html:
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

This suggstes linear, not constant time. Which is it?
--Mark

[Mike Brock]

An ArrayList encapsulates an Object[] internally, so the operation involved in doing a get() is fairly simple.
The single biggest implication to performance when it comes to adding new objects in an ArrayList is the concept of capacity.
ArrayList, as well as other collections in the JDK are designed to grow in size automatically when a certain load is reached (70% by default). Obviously, the introspection alone, required when an object is added will lead to some minor performance cost (very insignificant in most cases mind you). But when the array is forced to grow, (and you should take the terminology with a grain of salt) something happens of great cost to performance: A new array sized twice that of the original is created, and the contents are copied from the old array into the new. This is the main difference between the performance of a LinkedList and an ArrayList when it comes to adding elements. When you add an element to a linked list, a new node is create and referenced to the last node. Since there is no encapsulating data structure, this operation can occur progressively and at a constant rate; a linked list does not 'fill up' like and array, it just attaches on more elements to the end.
But all that said, which is better performing? That is a question of implementation. An array will always be superior for data access, which is why it is and always will be the single most important data structure in computing. An array is a sequential and 'contiguous' data structure in memory of equally sized elements. This makes traversal extremely computationally efficient. And inversely, a LinkedList is a sequential and 'non-contiguous' data structure in memory of potentially differently sized elements. So picking one or the other is an issue of understanding the problem with which you are faced. If you have a situation where unforseen amounts of differently sized data are being presented to you, a linked list is a much superior solution. Likewise, if you have a fixed-amount of consistantly sized data then the array is a logical solution.
I realize there are some simplifications in my explainations and suggestions for those knitpickers out there. But I hope this gives your a clearer understanding
Mike.
[ February 05, 2003: Message edited by: Mike Brock ]
[ February 05, 2003: Message edited by: Mike Brock ]

[Mark Herschberg]

Looking back, I missed where it listed "get" under constant time. Duh. So the documentation is consistent. It's been a loooooong day....
--Mark

[Joe Cheng]

Well, one thing that LinkedList does much better than ArrayList is insert elements at the top of the list. So a LinkedList would probably be the better choice for, say, a queue than ArrayList.