From RandomAccess API
It is recognized that the distinction between random and sequential access is often fuzzy. For example, some List implementations provide asymptotically linear access times if they get huge, but constant access times in practice. Such a List implementation should generally implement this interface. As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:
for (int i=0, n=list.size(); i < n; i++)
list.get(i);
runs faster than this loop:
for (Iterator i=list.iterator(); i.hasNext(); )
i.next();
Since they both measure time sequentially, how could the second loop run slower than the first loop? Suppose the first look is backed by an Array and the second loop is backed by a LinkedList. Accessing the next item on the list takes O(1) since it just follows the next pointer to the next element.