One of the concrete classes that implements Collection is java.util.LinkedList. This class is just a plain old “Data Structures 101” forward-and-backward-linked list. You provide separate objects that you want stored, and the library class does the work of setting up and copying references to make a list. You start by instantiating an empty LinkedList, then anything you add is put on the list as a new element.
The class LinkedList implements List which implements Collection. The exact parent-child relationship of interfaces is shown in Figure 16-1.
The interface java.util.List adds about another ten methods to the elementary data access methods specified in java.util.Collection. Slightly simplified, the methods are:
public interface java.util.List<E> extends java.util.Collection <E> {
public boolean addAll(int index, Collection);
public Object get(int index);
public Object set(int index, E element);
public void add(int index, E element);
public Object remove(int index);
public int indexOf(Object o);
public int lastIndexOf(Object o);
public java.util.ListIterator<E> listIterator();
public java.util.ListIterator<E> listIterator(int index);
public java.util.List<E> subList(int from, int to);
}
Most of these List methods let the programmer access elements by their integer index (position in the list), and search for elements in the list. Unlike sets, lists allow duplicate elements. Say you owned a store, and wanted to record each item as it is sold so that you know what you need to re-order. A list would be a good choice for this kind of collection. As you complete each sale, say for a 21-inch Sony color TV model ABC-1, a new element representing that product is added to the list. If you sell ten of them during the day, there will be 10 “TV model ABC-1” records on the list.
A HashSet would not be a good choice for this collection, because after you have added the first ABC-1 record to the collection, it's already in the set and you cannot add it again.
The subList() method returns a new list that points to the elements in the first list between the from argument, inclusive but not including the to argument. Lists start at element zero, just like arrays.
Note the two listIterator() methods. A ListIterator is a subinterface of Iterator. The first listIterator() obtains a ListIterator starting at the first element in the collection. The second one gets a ListIterator starting at the position specified by the int argument. Listiterator promises these methods:
public interface java.util.ListIterator<E> extends java.util.Iterator<E> {
public boolean hasNext();
public E next();
public boolean hasPrevious();
public E previous();
public int nextIndex();
public int previousIndex();
public void remove();
public void set(E e);
public void add(E e);
}
A ListIterator allows you to iterate backwards over a list of objects as well as forwards. If you want to start at the end of the list, create a ListIterator passing an argument of list.size(). Then a call to list.previous() will return the last element, and you can keep going back through previous objects.
Unlike an Iterator, a ListIterator doesn't have a current element. The position of the ListIterator always lies in between two elements: the one that would be returned by a call to coll.previous(), and the one that would be returned by a call to coll.next().
The remove() and set() methods operate on the element returned by the most recent next() or previous(). The set() method replaces that element by the argument element. The remove() method removes that element from the list.
Here is the code for iterating backwards through a list:
LinkedList <String> cs = new LinkedList<String>();
// code to add elements
cs.add( "hello" );
cs.add( "there" );
cs.add( "everybody" );
ListIterator<String> li = cs.listIterator( cs.size() );
while( li.hasPrevious() ) {
String s = li.previous();
System.out.println(s);
}
% javac -source 1.5 example.java
% java example
everybody
there
hello
We now come to another class that implements List. ArrayList is a concrete class that implements the List interface using an array as the underlying type. The ArrayList class should be thought of as an array that grows as needed to store the number of elements you want to put there.
When you want to put your data in a List, ArrayList is always an alternative to LinkedList. The reason for choosing one over the other is a performance versus function trade off.
-
An ArrayList offers immediate access to all its elements (they are stored in an array, remember). You can only reach a LinkedList element by starting at one end or the other of the list, and traversing all the intervening elements.
-
A LinkedList lets you add a new element very quickly. The time to add an element to an ArrayList is normally quick, too. But when the array is full, adding another element causes a new bigger array to be allocated and the old one copied over into it. LinkedList does not have that drawback.
The ArrayList class has the following public methods (slightly simplified to omit bounds on generic parameters), in addition to those promised by the List interface:
public class java.util.ArrayList<E> implements
java.util.List, java.util.RandomAccess,
java.lang.Cloneable, java.io.Serializable {
public ArrayList(); // constructors
public ArrayList(int size);
public ArrayList(Collection c);
public void trimToSize();
public void ensureCapacity(int size);
public Object clone();
}
You don't access ArrayList elements with the array brackets “[],” instead, you use the List methods to get and set the elements at particular indices.
To cut down on incremental reallocation, you can tell the constructor how many elements the array should allow for initially. The default allocation is ten elements, or 10% more than the size of a Collection you pass to the constructor, in the JDK.