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.
The quote is talking about comparing different ways of using a single implementation. Your example doesn't do that so it doesn't make sense. You could consider the comparison of the two pieces of code on an ArrayList, and then consider the comparison of the two pieces of code on a LinkedList. In fact you should.
Joined: Apr 19, 2005
That is what I was missing. Thanks for pointing it out. For ArrayList, it should not be much different since the runtime of both iterations will be equivalent; however, there is a big different for LinkedList
subject: Question on general advice of when to implement RandomAccess