package java.util;

/**
 * Marker interface used by <code>List</code> implementations to indicate that they support fast
 * (generally constant time) random access. The primary purpose of this interface is to allow
 * generic algorithms to alter their behavior to provide good performance when applied to either
 * random or sequential access lists.
 *
 * <p>
 * The best algorithms for manipulating random access lists (such as <code>ArrayList</code>) can produce
 * quadratic behavior when applied to sequential access lists (such as <code>LinkedList</code>). Generic
 * list algorithms are encouraged to check whether the given list is an <code>instanceof</code> this
 * interface before applying an algorithm that would provide poor performance if it were applied to
 * a sequential access list, and to alter their behavior if necessary to guarantee acceptable
 * performance.
 *
 * <p>
 * It is recognized that the distinction between random and sequential access is often fuzzy. For
 * example, some <code>List</code> implementations provide asymptotically linear access times if they
 * get huge, but constant access times in practice. Such a <code>List</code> implementation should
 * generally implement this interface. As a rule of thumb, a <code>List</code> implementation should
 * implement this interface if, for typical instances of the class, this loop:
 *
 * <pre>
 * for (int i = 0, n = list.size(); i &lt; n; i++)
 * 	list.get(i);
 * </pre>
 *
 * runs faster than this loop:
 *
 * <pre>
 * for (Iterator i = list.iterator(); i.hasNext();)
 * 	i.next();
 * </pre>
 *
 * <p>
 * This interface is a member of the Java Collections Framework
 */
public interface RandomAccess {
}