Collections - The Java Programming Language - page 864

Exercise 21.1 : Write a program that opens a file and reads its lines
one at a time, storing each line in a List sorted by String.compareTo . The
line-reading class you created for Exercise 20.4 should prove helpful.
21.6.3. RandomAccess Lists
The marker interface RandomAccess marks list implementations that sup-
port fast random access. Random access means that any element of the
list can be accessed directly. For example, ArrayList implements Ran-
domAccess because any element can easily be accessed by its index. In
contrast, a LinkedList does not implement RandomAccess because access-
ing an element by index requires traversing from one end of the list.
Some algorithms for manipulating random access lists perform poorly
when applied to sequential lists, so the purpose of the RandomAccess in-
terface is to allow an algorithm to adapt depending on the kind of list it
is given. As a rule of thumb, if code such as
for (int i = 0; i < list.size(); i++)
process(list.get(i));
will typically be faster than using
Iterator it = list.iterator();
while (it.hasNext())
process(it.next());
then your list should implement RandomAccess .