11.4 Lists

Lists are collections that maintain their elements in order, and can contain duplicates. The elements in a list are ordered. Each element, therefore, has a position in the list. A zero-based index can be used to access the element at the position designated by the index value. The position of an element can change as elements are inserted or deleted from the list.

In addition to the operations inherited from the Collection interface, the List interface also defines operations that work specifically on lists: position-based access of the list elements, searching in a list, creation of customized iterators, and operations on parts of a list (called open range-view operations). This additional functionality is provided by the following methods in the List interface:

// Element Access by Index
Object get(int index)

Returns the element at the specified index.

Object set(int index, Object element) Optional

Replaces the element at the specified index with the specified element. It returns the previous element at the specified index.

void add(int index, Object element) Optional

Inserts the specified element at the specified index. If necessary, it shifts the element previously at this index and any subsequent elements one position toward the end of the list. The inherited method add(Object) from the Collection interface will append the specified element to the end of the list.

Object remove(int index) Optional

Deletes and returns the element at the specified index, contracting the list accordingly. The inherited method remove(Object) from the Collection interface will remove the first occurrence of the element from the list.

boolean addAll(int index, Collection c) Optional

Inserts the elements from the specified collection at the specified index, using the iterator of the specified collection. The method returns true if any elements were added.

In a non-empty list, the first element is at index 0 and the last element is at size()-1. As might be expected, all methods throw an IndexOutOfBoundsException if an illegal index is specified.

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

These methods respectively return the index of the first and the last occurrence of the element in the list if the element is found; otherwise, the value ?1 is returned.

// List Iterators
ListIterator listIterator()
ListIterator listIterator(int index)

The iterator from the first method traverses the elements consecutively, starting with the first element of the list, whereas the iterator from the second method starts traversing the list from the element indicated by the specified index.

interface ListIterator extends Iterator {

    boolean hasNext();
    boolean hasPrevious();

    Object next();          // Element after the cursor
    Object previous();      // Element before the cursor

    int nextIndex();        // Index of element after the cursor
    int previousIndex();    // Index of element before the cursor

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

The ListIterator interface is a bidirectional iterator for lists. It extends the Iterator interface and allows the list to be traversed in either direction. When traversing lists, it can be helpful to imagine a cursor moving forward or backward between the elements when calls are made to the next() and the previous() method, respectively. The element that the cursor passes over is returned. When the remove() method is called, the element last passed over is removed from the list.

// Open Range-View
List subList(int fromIndex, int toIndex)

This method returns a view of the list, which consists of the sublist of the elements from the index fromIndex to the index toIndex-1. A view allows the range it represents in the underlying list to be manipulated. Any changes in the view are reflected in the underlying list, and vice versa. Views can be used to perform operations on specific ranges of a list.

`ArrayList`, `LinkedList`, and `Vector`

Three implementations of the List interface are provided in the java.util package: ArrayList, LinkedList, and Vector.

The ArrayList class implements the List interface. The Vector class is a legacy class that has been retrofitted to implement the List interface. The Vector and ArrayList classes are implemented using dynamically resizable arrays, providing fast random access and fast list traversal?very much like using an ordinary array. Unlike the ArrayList class, the Vector class is thread-safe, meaning that concurrent calls to the vector will not compromise its integrity.

The LinkedList implementation uses a doubly-linked list. Insertions and deletions in a doubly-linked list are very efficient?elements are not shifted, as is the case for an array. The LinkedList class provides extra methods that implement operations that add, get, and remove elements at either end of a LinkedList:

void addFirst(Object obj)
void addLast(Object obj)
Object getFirst()
Object getLast()
Object removeFirst()
Object removeLast()

The ArrayList and Vector classes offer comparable performance, but Vector objects suffer a slight performance penalty due to synchronization. Position-based access has constant-time performance for the ArrayList and Vector classes. However, position-based access is in linear time for a LinkedList, owing to traversal in a doubly-linked list. When frequent insertions and deletions occur inside a list, a LinkedList can be worth considering. In most cases, the ArrayList implementation is the over-all best choice for implementing lists.

The ArrayList class provides the following constructors:

ArrayList()

Constructs a new, empty ArrayList. An analogous constructor is provided by the LinkedList and Vector classes.

ArrayList(Collection c)

Constructs a new ArrayList containing the elements in the specified collection. The new ArrayList will retain any duplicates. The ordering in the ArrayList will be determined by the traversal order of the iterator for the collection passed as argument. An analogous constructor is provided by the LinkedList and Vector classes.

ArrayList(int initialCapacity)

Constructs a new, empty ArrayList with the specified initial capacity. An analogous constructor is provided by the Vector class.

Example 11.3 Using Lists

import java.util.*;

public class TakeAGuess {
    final static int NUM_DIGITS = 5;

    public static void main(String[] args) {

        // Sanity check on the given data.
        if (args.length != NUM_DIGITS) {
            System.err.println("Guess " + NUM_DIGITS + " digits.");
            return;
        }
        /* Initialize the solution list. This program has a fixed solution. */
        List secretSolution = new ArrayList();                      // (1)
        secretSolution.add("5");
        secretSolution.add("3");
        secretSolution.add("2");
        secretSolution.add("7");
        secretSolution.add("2");

        // Convert the user's guess from string array to list.         (2)
        List guess = new ArrayList();
        for (int i=0; i<NUM_DIGITS; i++)
            guess.add(args[i]);

        // Find the number of digits that were correctly included.     (3)
        List duplicate = new ArrayList(secretSolution);
        int numIncluded = 0;
        for (int i=0; i<NUM_DIGITS; i++)
            if (duplicate.remove(guess.get(i))) numIncluded++;

        /* Find the number of correctly placed digits by comparing the two
           lists, element by element, counting each correct placement. */
        // Need two iterators to traverse through guess and solution.  (4)
        ListIterator correct = secretSolution.listIterator();
        ListIterator attempt = guess.listIterator();
        int numPlaced = 0;
        while (correct.hasNext())
            if (correct.next().equals(attempt.next())) numPlaced++;

        // Print the results.
        System.out.println(numIncluded + " digit(s) correctly included.");
        System.out.println(numPlaced +   " digit(s) correctly placed.");
    }
}

Running the program with the following arguments:

java TakeAGuess 3 2 2 2 7

gives the following output:

4 digit(s) correctly included.
1 digit(s) correctly placed.

Example 11.3 illustrates some basic operations on lists. The user gets one shot at guessing a five-digit code. The solution is hard-wired in the example as a list of five elements, where each element represents a digit as a String object. The secretSolution list is created at (1) and populated using the add() method. The guess specified at the command line is placed in a separate list, called guess, at (2).

The number of digits that are correctly guessed is determined at (3). The solution is first duplicated and each digit in the guess is removed from the duplicated solution. The number of deletions corresponds to the number of correct digits in the guess list. A digit at a particular index in the guess list is returned by the get() method. The remove() method returns true if the duplicate list was modified, that is, the digit from the guess was found and removed from the duplicated solution.

// Find the number of digits that were correctly included.     (3)
List duplicate = new ArrayList(secretSolution);
int numIncluded = 0;
for (int i=0; i<NUM_DIGITS; i++)
    if (duplicate.remove(guess.get(i))) numIncluded++;

Finding the number of digits that are correctly placed is achieved by using two list iterators, which allow digits in the same position in the guess and the secretSolution lists to be compared:

// Need two iterators to traverse through guess and solution.    (4)
ListIterator correct = secretSolution.listIterator();
ListIterator attempt = guess.listIterator();
int numPlaced = 0;
while (correct.hasNext())
    if (correct.next().equals(attempt.next())) numPlaced++;