IMO the documentation here is poorly written. An iterator returned be an ArrayList uses calls to get(index) behind the scenes. But for the additional overhead of the Iterator object the difference in performace of the two loops should be unnoticable. I would say :
As a rule of thumb, a List implementation should implement this interface if, elements can be accessed by get(index) in more or less constant (O(1)) time.
The marker interface has no functionality, but it does serve as an indicator as to which algorithms should give better performance. For instance if you receive a sorted List and you want to find a particular element, if the List is random access then a binary search will be the optimal solution, however that would be a totally inappropriate choice for a sequential list. The JVM does nothing to optimize the performance of lists tagged as RandomAccess.
[ March 21, 2007: Message edited by: Garrett Rowe ]