Java Reference
In-Depth Information
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 view:
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
Class
Representation
Since
Random
access
Notes
Array
1.2
Yes
Best all-around implementation.
ArrayList
Double-linked list
1.2
No Eicient insertion and deletion.
LinkedList
Array
5.0
Yes
Threadsafe; fast traversal, slow modiication.
CopyOnWri
teArray
List
Array
1.0
Yes
Legacy class; synchronized methods. Do not use.
Vector