aspose file tools*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Question on general advice of when to implement RandomAccess Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Question on general advice of when to implement RandomAccess" Watch "Question on general advice of when to implement RandomAccess" New topic
Author

Question on general advice of when to implement RandomAccess

vu lee
Ranch Hand

Joined: Apr 19, 2005
Posts: 189
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.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18114
    
    8

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.
vu lee
Ranch Hand

Joined: Apr 19, 2005
Posts: 189
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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Question on general advice of when to implement RandomAccess
 
Similar Threads
How Random Access works
Random Access
Dealing out random, non-repeating cards
List iteration
Difference between ArrayList and LinkedList?