Java Reference
In-Depth Information
In other words, we need to have a method that constructs an iterator for our collec-
tion. We'll discuss later in this section how to do that for a linked list. Under the
hood, the for-each loop actually calls the iterator method on the collection and
yields each next element to the loop's body.
In this case we want our two classes to implement both the List<E> interface and
the Iterable<E> interface. The usual way to accomplish that in Java is to have one
interface extend another. This is similar to inheritance for classes and you use the
same extends keyword. Here is the complete List<E> specification:
1 // Generic interface for a List of objects of type E.
2
3 public interface List<E> extends Iterable<E> {
4 public int size();
5 public E get( int index);
6 public int indexOf(E value);
7 public boolean isEmpty();
8 public boolean contains(E value);
9 public void add(E value);
10 public void add( int index, E value);
11 public void addAll(List<E> other);
12 public void remove( int index);
13 public void set( int index, E value);
14 public void clear();
15 }
Notice that the header mentions that it extends the Iterable<E> interface. That
means that any class implementing the interface must provide a method for construct-
ing an iterator, which will allow the class to be used in for-each loops.
Before we write the actual code for LinkedList<E> , we'll explore some varia-
tions on linked lists and discuss the issue of iterators.
Linked List Variations
So far in this chapter, we have discussed the simplest possible linked list. Each
node in this list has had a single link to the next value in the list, and we have ter-
minated each list with the value null . We have used the value null to represent an
empty list.
However, there are many variations on linked lists. Several of these ideas are used
in Sun's implementation of LinkedList, and we will use several for our own imple-
mentation. There are three primary variations: circular lists, lists with dummy nodes,
and doubly linked lists. Let's consider each variation in turn.
Instead of making the final element of the list store the value null ,we
can have the final element of the list point back to the first value in the list. We
refer to such a list as circular . For example, here is a circular list that stores the
values [3, 7, 12]:
 
Search WWH ::




Custom Search