Interfaces

The List Interface

A Listis an ordered Collection(sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations for:

• Positional Access: manipulate elements based on their numerical position in the list.
• Search: search for a specified object in the list and return its numerical position.
• List Iteration: extend Iterator semantics to take advantage of the list's sequential nature.
• Range-view: perform arbitrary range operations on the list.

The List interface is shown below:

public interface List extends Collection {
    // Positional Access
    Object get(int index);
    Object set(int index, Object element);            // Optional
    void add(int index, Object element);              // Optional
    Object remove(int index);                         // Optional
    abstract boolean addAll(int index, Collection c); // Optional

    // Search
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // Iteration
    ListIterator listIterator();
    ListIterator listIterator(int index);

    // Range-view
    List subList(int from, int to);
}

The JDK contains two general-purpose List implementations. ArrayList, which is generally the best-performing implementation, and LinkedListwhich offers better performance under certain circumstances. Also, Vector has been retrofitted to implement List. For more information on implementations, see the Implementations lesson.

Comparison to Vector

If you've used Vector, you're already familiar with the general flavor of List. (Of course, List is an interface, while Vector is a concrete implementation.) List fixes several minor API deficiencies in Vector. For starters, commonly used Vector operations such as elementAt and setElementAt have been given much shorter names. When you consider that these two operations are the List analogue of square brackets for arrays, it becomes apparent that shorter names are highly desirable. Consider the following assignment statement:

    a[i] = a[j].times(a[k]);

The Vector equivalent is:

    v.setElementAt(v.elementAt(j).times(v.elementAt(k)), i);

The List equivalent is:

    v.set(i, v.get(j).times(v.get(k)));

You may already have noticed that the set method, which replaces setElementAt, reverses the order of the arguments so that they match the corresponding array operation. Consider this assignment statement:

    beatle[5] = "Billy Preston";

The Vector equivalent is:

    beatle.setElementAt("Billy Preston", 5);

The List equivalent is:

    beatle.set(5, "Billy Preston");

For consistency's sake, the add(int, Object) method, which replaces insertElementAt(Object, int), also reverses the order of the arguments.

The various range operations in Vector (indexOf, lastIndexOf(setSize) have been replaced by a single range-view operation (subList), which is far more powerful and consistent.

Collection Operations

The operations inherited from Collection all do about what you'd expect them to do, assuming you're already familiar with them from Collection. If you're not familiar with them, now would be a good time to read the lesson on the Collection interface. The remove operation always removes the first occurrence of the specified element from the list. The add and addAll operations always append the new element(s) to the end of the list. Thus, the following idiom concatenates one list to another:

list1.addAll(list2);

Here's a non-destructive form of this idiom, which produces a third List consisting of the second list appended to the first:

List list3 = new ArrayList(list1);
list3.addAll(list2);

Note that the idiom, in its non-destructive form, takes advantage of ArrayList's standard Collection constructor.

Like the Setinterface, List strengthens the requirements on the equals and hashCode methods so that two List objects can be compared for logical equality without regard to their implementation classes. Two List objects are equal if they contain the same elements in the same order.

Positional Access and Search Operations

The basic positional access operations (get, set, add and remove) behave just like their longer-named counterparts in Vector (elementAt, setElementAt, insertElementAt and removeElementAt) with one noteworthy exception. The set and remove operations return the old value that is being overwritten or removed; the Vector counterparts (setElementAt and removeElementAt) return nothing (void). The search operations indexOf and lastIndexOf behave exactly like the identically named operations in Vector.

The addAll operation inserts all of the elements of the specified Collection starting at the specified position. The elements are inserted in the order they are returned by the specified Collection's iterator. This call is the positional access analogue of Collection's addAll operation.

Here's a little function to swap two indexed values in a List. It should look familiar from Programming 101 (assuming you stayed awake):

private static void swap(List a, int i, int j) {
    Object tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

Of course there's one big difference. This is a polymorphic algorithm: it swaps two elements in any List, regardless of its implementation type. "Big deal," you say, "What's it good for?" Funny you should ask. Take a look at this:

public static void shuffle(List list, Random rnd) {
    for (int i=list.size(); i>1; i--)
        swap(list, i-1, rnd.nextInt(i));
}

This algorithm (which is included in the JDK's Collectionsclass) randomly permutes the specified List using the specified source of randomness. It's a bit subtle: It runs up the list from the bottom, repeatedly swapping a randomly selected element into the current position. Unlike most naive attempts at shuffling, it's fair (all permutations occur with equal likelihood, assuming an unbiased source of randomness) and fast (requiring exactly list.size()-1 iterations). The following short program uses this algorithm to print the words in its argument list in random order:

import java.util.*;

public class Shuffle {
    public static void main(String args[]) {
        List l = new ArrayList();
        for (int i=0; i<args.length; i++)
            l.add(args[i]);
        Collections.shuffle(l, new Random());
        System.out.println(l);
    }
}

In fact, we can make this program even shorter and faster. The Arraysclass has a static factory method called asList that allows an array to be viewed as a List. This method does not copy the array; changes in the List write through to the array, and vice-versa. The resulting List is not a general-purpose List implementation, in that it doesn't implement the (optional) add and remove operations: arrays are not resizable. Taking advantage of Arrays.asList and calling an alternate form of shuffle that uses a default source of randomness, you get the following tiny program, whose behavior is identical to the previous program:

import java.util.*;

public class Shuffle {
    public static void main(String args[]) {
        List l = Arrays.asList(args);
        Collections.shuffle(l);
        System.out.println(l);
    }
}

Iterators

As you'd expect, the Iterator returned by List's iterator operation returns the elements of the list in proper sequence. Additionally, List provides a richer iterator, called a ListIterator, that allows you to traverse the list in either direction, modify the list during iteration, and obtain the current position of the iterator. The ListIterator interface is summarized below (including the three methods it inherits from Iterator):

public interface ListIterator extends Iterator {
    boolean hasNext();
    Object next();

    boolean hasPrevious();
    Object previous();

    int nextIndex();
    int previousIndex();

    void remove();          // Optional
    void set(Object o);     // Optional
    void add(Object o);     // Optional
}

The three methods that ListIterator inherits from Iterator (hasNext, next, and remove) are intended to do exactly the same thing in both interfaces. The hasPrevious and previous operations are exact analogues of hasNext and next. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. The previous operation moves the cursor backwards whereas next moves it forwards.

Here's the standard idiom for iterating backwards through a list:

for (ListIterator i=l.listIterator(l.size()); i.hasPrevious(); ) {
    Foo f = (Foo) i.previous();
    ...
}

Note the argument to listIterator in the above idiom. The List interface has two forms of the listIterator method. The form with no arguments returns a ListIterator positioned at the beginning of the list, and the form with an int argument returns a ListIterator positioned at the specified index. The index refers to the element that would be returned by an initial call to next. If the index value of n is used, then the initial call to next would return null, since it would point just past the end of the list. An initial call to previous would return the element whose index was index-1. In a list of length n, there are n+1 valid values for index, from 0 to n, inclusive.

Intuitively speaking, the cursor is always between two elements, the one that would be returned by a call to previous and the one that would be returned by a call to next. The n+1 valid index values correspond to the n+1 "gaps" between elements, from the gap before the first element to the gap after the last one. The diagram below shows the five possible cursor positions in a list containing four elements.

           Element(0)   Element(1)   Element(2)   Element(3)   
         ^            ^            ^            ^            ^
  Index: 0            1            2            3            4

Calls to next and previous can be intermixed, but you have to be a bit careful. The first call to previous after a sequence of calls to next returns the same element as the last call to next. Similarly, the first call to next after a sequence of calls to previous returns the same element as the last call to previous. This will become obvious if you stare at the foregoing text long enough. If it doesn't, go get yourself a steaming hot mug of Java, and try again.

It should come as no surprise that the nextIndex method returns the index of the element that would be returned by a subsequent call to next, and previousIndex returns the index of the element that would be returned by a subsequent call to previous. These calls are typically used for one of two purposes: To report the position where something was found, or to record the position of the ListIterator so that another ListIterator with identical position can be created.

It should also come as no surprise that the number returned by nextIndex is always one greater than the number returned by previousIndex. This implies the behavior of the two boundary cases: a call to previousIndex when the cursor is before the initial element returns -1, and a call to nextIndex when the cursor is after the final element returns list.size()+1. To make all of this concrete, here's a possible implementation of List.indexOf:

public int indexOf(Object o) {
    for (ListIterator i = listIterator(); i.hasNext(); )
        if (o==null ? i.next()==null : o.equals(i.next()))
            return i.previousIndex();

    return -1; // Object not found
}

Note that the indexOf method returns i.previousIndex() though it is traversing the list in the forward direction. This is because i.nextIndex() would return the index of the element that we are about to examine, and we want to return the index of the element that we just examined.

The Iterator interface provides the remove operation to remove from the Collection the last element returned by next. The ListIterator interface provides two additional operations to modify the list: set and add. The set method "overwrites" the last element returned by next or previous with the specified element. It is demonstrated by the following polymorphic algorithm to replace all occurrences of one specified value with another:

public static void replace(List l, Object val, Object newVal) {
    for (ListIterator i = l.listIterator(); i.hasNext(); )
        if (val==null ? i.next()==null : val.equals(i.next()))
            i.set(newVal);
}

The only bit of trickiness in this example is the equality test between val and i.next. We have to special-case an val value of null in order to prevent a NullPointerException.

The add method inserts a new element into the list, immediately before the current cursor position. This method is illustrated in the following polymorphic algorithm to replace all occurrences of a specified value with the sequence of values contained in the specified list:

public static void replace(List l, Object val, List newVals) {
    for (ListIterator i = l.listIterator(); i.hasNext(); ) {
        if (val==null ? i.next()==null : val.equals(i.next())) {
            i.remove();
            for (Iterator j = newVals.iterator(); j.hasNext(); )
                i.add(j.next());
        }
    }
}

Range-view Operation

The range-view operation, subList(int fromIndex, int toIndex), returns a List view of the portion of this list whose indices range from fromIndex, inclusive, to toIndex, exclusive. This half-open range mirrors the typical for-loop:

for (int i=fromIndex; i<toIndex; i++) {
    ...
}

As the term view implies, the returned List is backed by the List on which subList was called, so changes in the former List are reflected in the latter.

This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List. For example, the following idiom removes a range of elements from a list:

list.subList(fromIndex, toIndex).clear();

Similar idioms may be constructed to search for an element in a range:

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

Note that the above idioms return the index of the found element in the subList, not the index in the backing List.

Any polymorphic algorithm that operates on a List (like the replace and shuffle examples, above) works with the List returned by subList.

Here's a polymorphic algorithm whose implementation uses subList to deal a hand from a deck. That is to say, it returns a new List (the "hand") containing the specified number of elements taken from the end of the specified List (the "deck"). The elements returned in the hand are removed from the deck.

public static List dealHand(List deck, int n) {
    int deckSize = deck.size();
    List handView = deck.subList(deckSize-n, deckSize);
    List hand = new ArrayList(handView);
    handView.clear();
    return hand;
}

The literal-minded might say that this program deals from the bottom of the deck, but I prefer to think that the computer is holding the deck upside down. At any rate, for many common List implementations, like ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.

Here's a program using the dealHand method in combination with Collections.shuffle to generate hands from a normal 52-card deck. The program takes two command line arguments: the number of hands to deal and the number of cards in each hand.

import java.util.*;

class Deal {
    public static void main(String args[]) {
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);

       // Make a normal 52-card deck
        String[] suit = new String[] {"spades", "hearts", "diamonds", "clubs"};
        String[] rank = new String[]
            {"ace","2","3","4","5","6","7","8","9","10","jack","queen","king"};
        List deck = new ArrayList();
        for (int i=0; i<suit.length; i++)
            for (int j=0; j<rank.length; j++)
                deck.add(rank[j] + " of " + suit[i]);

        Collections.shuffle(deck);

        for (int i=0; i<numHands; i++)
            System.out.println(dealHand(deck, cardsPerHand));
    }
}

Let's run the program:

% java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades, king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts, queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds, 9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts, ace of hearts]

While the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List. Thus, it's highly recommended that you use the List returned by subList only as a transient object, to perform one or a sequence of range operations on the backing List. The longer you use the subList object, the greater the probability that you'll compromise it by modifying the backing List directly (or through another subList object).

Algorithms

Most of the polymorphic algorithms in the Collections class apply specifically to List. Having all of these algorithms at your disposal makes it very easy to manipulate lists. Here's a summary of these algorithms, which are described in more detail in the Algorithms lesson.

• sort(List): Sorts a List using a merge sort algorithm, which provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)
• shuffle(List): Randomly permutes the elements in a List. (Shown above.)
• reverse(List): Reverses the order of the elements in a List.
• fill(List, Object): Overwrites every element in a List with the specified value.
• copy(List dest, List src): Copies the source List into the destination List.
• binarySearch(List, Object): Searches for an element in an ordered List using the binary search algorithm.

Contents