List
implementations are grouped into general-purpose and special-purpose implementations.General-Purpose List Implementations
There are two general-purposeList
implementations ArrayList
andLinkedList
. Most of the time, you'll probably useArrayList
, which offers constant-time positional access and is just plain fast. It does not have to allocate a node object for each element in theList
, and it can take advantage ofSystem.arraycopy
when it has to move multiple elements at the same time. Think ofArrayList
asVector
without the synchronization overhead.If you frequently add elements to the beginning of the
List
or iterate over theList
to delete elements from its interior, you should consider usingLinkedList
. These operations require constant-time in aLinkedList
and linear-time in anArrayList
. But you pay a big price in performance. Positional access requires linear-time in aLinkedList
and constant-time in anArrayList
. Furthermore, the constant factor forLinkedList
is much worse. If you think you want to use aLinkedList
, measure the performance of your application with bothLinkedList
andArrayList
before making your choice:ArrayList
is usually faster.
ArrayList
has one tuning parameter the initial capacity, which refers to the number of elements theArrayList
can hold before it has to grow.LinkedList
has no tuning parameters and seven optional operations, one of which isclone
. The other six areaddFirst
,getFirst
,removeFirst
,addLast
,getLast
, andremoveLast
.LinkedList
also implements theQueue
interface.Special-Purpose List Implementations
CopyOnWriteArrayList
is aList
implementation backed up by a copy-on-write array. This implementation is similar in nature toCopyOnWriteArraySet
. No synchronization is necessary, even during iteration, and iterators are guaranteed never to throwConcurrentModificationException
. This implementation is well suited to maintaining event-handler lists, in which change is infrequent, and traversal is frequent and potentially time-consuming.If you need synchronization, a
Vector
will be slightly faster than anArrayList
synchronized withCollections.synchronizedList
. ButVector
has loads of legacy operations, so be careful to always manipulate theVector
with theList
interface, or you won't be able to replace the implementation at a later time.If your
List
is fixed in size that is, you'll never useremove
,add
, or any of the bulk operations other thancontainsAll
you have a third option that's definitely worth considering. SeeArrays.asList
in the Convenience Implementations section for more information.