Random access to Lists
A general expectation of List implementations is that they can be efficiently iter‐
ated, typically in time proportional to the size of the list. Lists do not all provide effi‐
cient random access to the elements at any index, however. Sequential-access lists,
such as the LinkedList class, provide efficient insertion and deletion operations at
the expense of random-access performance. Implementations that provide efficient
random access implement the RandomAccess marker interface, and you can test for
this interface with instanceof if you need to ensure efficient list manipulations:
// Arbitrary list we're passed to manipulate
List <?> l = ...;
// Ensure we can do efficient random access. If not, use a copy
// constructor to make a random-access copy of the list before
// manipulating it.
if (!( l instanceof RandomAccess )) l = new ArrayList <?>( l );
The Iterator returned by the iterator() method of a List iterates the list ele‐
ments in the order that they occur in the list. List implements Iterable , and lists
can be iterated with a foreach loop just as any other collection can.
To iterate just a portion of a list, you can use the subList() method to create a sub‐
List < String > words = ...; // Get a list to iterate
// Iterate just all elements of the list but the first
for ( String word : words . subList ( 1 , words . size ))
System . out . println ( word );
Table 8-2 summarizes the five general-purpose List implementations in the Java
platform. Vector and Stack are legacy implementations and should not be used.
CopyOnWriteArrayList is part of the java.util.concurrent package and is only
really suitable for multithreaded use cases.
Table 8-2. List implementations
Best all-around implementation.
No Eicient insertion and deletion.
Threadsafe; fast traversal, slow modiication.
Legacy class; synchronized methods. Do not use.