The collections api - Data Structures and Problem Solving Using Java - page 252

Now an arbitrary item can no longer be found in one access. Instead, we must
scan down the list. This is similar to the difference between accessing an item on a
compact disk (one access) or a tape (sequential). While this may appear to make
linked lists less attractive than arrays, they still have advantages. First, an insertion
into the middle of the list does not require moving all of the items that follow the
insertion point. Data movement is very expensive in practice, and the linked list
allows insertion with only a constant number of assignment statements.

Comparing ArrayList and LinkedList , we see that insertions and deletions
toward the middle of the sequence are inefficient in the ArrayList but may be
efficient for a LinkedList . However, an ArrayList allows direct access by the
index, but a LinkedList should not. It happens that in the Collections API, get
and set are part of the List interface, so LinkedList supports these operations,
but does so very slowly. Thus, the LinkedList can always be used unless effi-
cient indexing is needed. The ArrayList may still be a better choice if inser-
tions occur only at the end.
To access items in the list, we need a reference to the corresponding node,
rather than an index. The reference to the node would typically be hidden
inside an iterator class.

The basic trade-
off between
ArrayList and
LinkedList is that
get is not efficient
for LinkedList ,
while insertion and
removal from the
middle of a con-
tainer is more effi-
ciently supported
by the LinkedList .

Because LinkedList performs add s and remove s more efficiently, it has more
operations than the ArrayList . Some of the additional operations available for
LinkedList are the following:

Access to the list
is done through an
iterator class.

void addLast( AnyType element )
Appends element at the end of this LinkedList .

void addFirst( AnyType element )
Appends element to the front of this LinkedList .

AnyType getFirst( )
AnyType element( )
Returns the first element in this LinkedList . element was added in Java 5.

AnyType getLast( )
Returns the last element in this LinkedList .

AnyType removeFirst( )
AnyType remove( )
Removes and returns the first element from this LinkedList . remove was
added in Java 5.

AnyType removeLast( )
Removes and returns the last element from this LinkedList .

We implement the LinkedList class in Part Four.