Java Reference
In-Depth Information
ArrayList is a powerful and useful collection, but there are some cases in which
using an ArrayList isn't ideal. For example, suppose we want to write a program to
remove each String of even length from an ArrayList of String s. We can do this
by using a loop that examines each element of the list and either removes it if its
length is even or advances to the next string if its length is odd:
// Removes all strings of even length from the given list.
public static void removeEvenLength(ArrayList<String> list) {
int i = 0;
while (i < list.size()) {
String element = list.get(i);
if (element.length() % 2 == 0) {
list.remove(i);
} else {
i++; // skip to next element
}
}
}
The preceding code is correct, but it doesn't perform well when the list has a lot of
elements. On a relatively modern machine, it can take several minutes to process a
list of a million elements. The reason it is so slow is that every time we remove an
element from the list, we have to shift all subsequent elements to the left by one. This
repeated shifting results in a slow program.
Another case in which an ArrayList behaves slowly is when it's used to model a
waiting line or queue, where elements (customers) are always added to the end of the
list (line) and always removed from the front. As customers arrive, they are added to
the end of the list. Customers are removed from the front of the list and processed in
turn. Removing an element from the front of a large ArrayList is a slow operation
because all the other elements have to be shifted to the left.
Another type of collection, called a linked list, can give better performance in prob-
lems like these that involve a lot of additions to or removals from the front or middle of
a list. A linked list provides the same operations as an array list, such as add , remove ,
isEmpty , size , and contains . But a linked list stores its elements in a fundamentally
different way. Elements of a linked list are stored in small individual containers called
nodes. The nodes are “linked” together, each node storing a reference to the next node
in the list. The overall linked list object keeps references to the front and back nodes.
Linked List
A collection that stores a list of elements in small object containers called
nodes, which are linked together.
You can envision a linked list as an array list that's been “broken apart,” with each
element then stored in a small box (a node) connected to its neighboring box by an arrow.
 
Search WWH ::




Custom Search