Java Collections Framework - Building Java Programs: A Back to Basics Approach - page 681

Iterators
As we discussed in Chapter 7, arrays provide a nice property called random access,
meaning that we can efficiently access or modify arbitrary array elements in any order.
This access is possible because arrays are stored as large contiguous blocks of memory,
so the computer can quickly compute the memory location of any of the array's
elements. Linked lists, unfortunately, do not provide fast random access. A linked list
is made up of many small node objects and generally keeps a direct reference only to
one or two particular elements, such as the front and back elements. Therefore it is not
possible to quickly access arbitrary elements of the list. A linked list is somewhat like
a VHS tape or audio cassette tape in this way; if we wish to access an element, we
must “fast-forward” or “rewind” through the list to the proper position.
When you call a method like get , set , add , or remove on a linked list, the code
internally creates a temporary reference that begins at the front of the list and trav-
erses the links between nodes until it reaches the desired index. The amount of time
that this takes depends on the index you chose: If you ask for the element at index 5 it
will be returned quickly, but if you ask for the element at index 9,000 the loop inside
the get method must advance through 9,000 nodes, which will take much longer.
These methods tend to be slow when you use them on a linked list, especially if
you call them many times or call them on a list with many elements. Imagine that
after the preceding example call of get(9000) you decided to call get(9001) . The
linked list doesn't remember its previous position, so it starts from the front again
and advances 9,001 times. The only case in which the methods run quickly is when
you pass an index near the front or back of the list.
Earlier in this chapter, we wrote a method to remove strings of even length from
an ArrayList . If we adapted this code to use a LinkedList and made no other
modifications we would find that it still runs very slowly on large lists, because it
calls the get and remove methods many times:
// performs poorly on a linked list
public static void removeEvenLength(LinkedList<String> list) {
int i = 0;
while (i < list.size()) {
String element = list.get(i); // slow
if (element.length() % 2 == 0) {
list.remove(i); // slow
} else {
i++;
}
}
}
However, there's an efficient way to examine every element of a linked list if we
want sequential access (i.e., if we want to examine each element in order from the
front to the back). To perform this task, we can use a special object called an iterator
that keeps track of our current position in the list.