The ArrayList, LinkedList, and Vector Classes – Collections: Part II


The ArrayList<E>, LinkedList<E>, and Vector<E> Classes

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

The ArrayList<E> class implements the List<E> interface (Chapter 12, p. 643). The Vector<E> class is a legacy class that has been retrofitted to implement the List<E> interface, and will not be discussed in detail. The Vector<E> and ArrayList<E> classes are implemented using dynamically resizable arrays, providing fast random access by index (i.e., position-based access) and fast list iteration—very much like using an ordinary array. Unlike the ArrayList<E> class, the Vector<E> class is thread-safe, meaning that concurrent calls to the vector will not compromise its integrity. The LinkedList<E> implementation uses a doubly linked list. Insertions and deletions in a doubly linked list are very efficient.

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

In addition to the List<E> interface, the LinkedList<E> class also implements two other interfaces that allow it to be used for stacks and different kinds of queues (p. 814).

Example 15.3 illustrates some basic operations on lists. The user gets one shot at guessing a five-digit code. The solution is hardwired in the example as a list of five Integer objects. The secretSolution list is created at (1), and populated using the Collections.addAll() static method (p. 862). 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. Of course, one could use the retainAll() method, as shown below, but the idea in Example 15.3 is to use positional access on the guess list.

Click here to view code image

// Find the number of digits that were correctly included.                 (3)
List<Integer> duplicate = new ArrayList<>(secretSolution);
duplicate.retainAll(guess);
numOfDigitsIncluded = duplicate.size();

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

Example 15.3 Using Lists

Click here to view code image

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
public class TakeAGuess {
  static final int NUM_DIGITS = 5;
  public static void main(String[] args) {
    // Sanity check on the given data.
    try {
      if (args.length != 1 || args[0].length() != NUM_DIGITS)
        throw new IllegalArgumentException();
      Integer.parseInt(args[0]);
    } catch(IllegalArgumentException nfe) {
      System.err.println(“Guess should be ” + NUM_DIGITS + ” digits.”);
      return;
    }
    String guessStr = args[0];
    System.out.println(“Guess: ” + guessStr);
    /* Initialize the solution list. This program has a fixed solution: 53272 */
    List<Integer> secretSolution = new ArrayList<>();                       // (1)
    Collections.addAll(secretSolution, 5, 3, 2, 7, 2);
    // Convert the guess from string to a list of Integers.                    (2)
    List<Integer> guess = new ArrayList<>();
    for (int i = 0; i < guessStr.length(); i++)
      guess.add(Character.getNumericValue(guessStr.charAt(i)));
    // Find the number of digits that were correctly included.                 (3)
    List<Integer> duplicate = new ArrayList<>(secretSolution);
    int numOfDigitsIncluded = 0;
    for (int i = 0; i < NUM_DIGITS; i++)
      if (duplicate.remove(guess.get(i))) numOfDigitsIncluded++;
    /* Find the number of digits correctly placed by comparing the two
       lists, element by element, counting each correct placement. */
    // Need two iterators to traverse through the guess and solution lists.    (4)
    ListIterator<Integer> correct = secretSolution.listIterator();
    ListIterator<Integer> attempt = guess.listIterator();
    int numOfDigitsPlaced = 0;
    while (correct.hasNext())
      if (correct.next().equals(attempt.next())) numOfDigitsPlaced++;
    // Print the results.
    System.out.println(numOfDigitsIncluded + ” digit(s) correctly included.”);
    System.out.println(numOfDigitsPlaced +   ” digit(s) correctly placed.”);
  }
}

Running the program with the following command:

>
java TakeAGuess 32227

gives the following output:

Click here to view code image
Guess: 32227
4 digit(s) correctly included.
1 digit(s) correctly placed.

Leave a Reply

Your email address will not be published. Required fields are marked *