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

6.5.2 LinkedList class

There are two basic List implementations in the Collections API. One imple-
mentation is the ArrayList , which we have already seen. The other is a
LinkedList , which stores items internally in a different manner than ArrayList ,
yielding performance trade-offs. A third version is Vector , which is like
ArrayList , but is from an older library, and is present mostly for compatibility
with legacy (old) code. Using Vector is no longer in vogue.

The ArrayList may be appropriate if insertions are performed only at the
high end of the array (using add ), for the reasons discussed in Section 2.4.3. The
ArrayList doubles the internal array capacity if an insertion at the high end
would exceed the internal capacity. Although this gives good Big-Oh perfor-
mance, especially if we add a constructor that allows the caller to suggest initial
capacity for the internal array, the ArrayList is a poor choice if insertions are not
made at the end, because then we must move items out of the way.

The LinkedList
class implements
a linked list.

In a linked list, we store items noncontiguously rather than in the
usual contiguous array. To do this, we store each object in a node that con-
tains the object and a reference to the next node in the list, as shown in
Figure 6.19. In this scenario, we maintain references to both the first and
last node in the list.
To be more concrete, a typical node looks like this:

The linked list is
used to avoid large
amounts of data
movement. It
stores items with
an additional one
reference per item
overhead.

class ListNode
{
Object data; // Some element
ListNode next;
}

At any point, we can add a new last item x by doing this:

last.next = new ListNode( ); // Attach a new ListNode
last = last.next; // Adjust last
last.data = x; // Place x in the node
last.next = null; // It's the last; adjust next

figure 6.19
A simple linked list

A0 A1 A2 A3

first last