Interface RandomAccess

 Interface RandomAccess

All Known Implementing Classes:

ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector

---

public interface RandomAccess

This is a marker interface that is used by it's implementors, to support fast(generally constant time) access to the data-structure implemented by all known implementing classes ; The primary purpose of this interface is to provide better performance.

Generic list algorithms are encouraged to check whether the given list is an instanceOf this interface. It applies an algorithm based on the condition check that whether the RandomAccess interface is implemented or not; If the interface is implemented then based on that check we can apply an algorithm to guarantee acceptable performance.

In essence the instanceOf operator controls the application of the random-access algorithms. If a class or interface extends the RandomAccess marker interface. We generally use the conditional execution of the algorithms.

It has been observed that the distinction between random and sequential access  is quite narrow but with a considerably large input, the difference is significant.

For example, some List implementations provide asymptotically linear access times or in terms of the Big O Notation of N (O(n)) if their size gets huge; But  some operations support 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, the following loop .. continued..

     for (int i=0, n=list.size(); i < n; i++)
         list.get(i);
 

..continued :: runs faster than this loop:

     for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();
 

So please copy the above code and monitor the execution time for the above two loops using system.getcurrenttimemillis()