The Java Collections framework supplies two kinds of List implementations, ArrayList and LinkedList. ArrayList and LinkedList are both substitutable for List. This lab explores the question: Why do we need two different implementations of List?

Study the following program that reads in a dictionary of English words (about 110,000 words), allows the user to store the words in either an ArrayList or a LinkedList, searches for and counts the number of words in the dictionary that start with a user-supplied string, and records the amount of time (in nanoseconds) required to perform the search; for example:

java StartsWtih linked arm
Took 18675842 ns to find 68 words starting with arm using a LinkedList

java StartsWith array arm
Took 17692683 ns to find 68 words starting with arm using a ArrayList

Pay particular attention to the comments in blue and the code in red.

import java.util.*;
import java.io.*;

public class StartsWith
{
   public static void main(String[] args) throws IOException
   {
      PrintStream out = System.out;
      
      if (args.length != 2)
      {
         out.println("Usage: java Dictionary <list-type> <starts-with>");
         out.println("where <list-type> is linked or array");
         System.exit(1);
      }
      
      // Create the dictionary list
      // Notice the use of substitutability: Dictionary is declared as List,
      // but actually refers to either an ArrayList or a LinkedList
      String listType = "ArrayList";
      List<String> dictionary = new ArrayList<String>();
      if (args[0].equals("linked"))
      {
         listType = "LinkedList";
         dictionary = new LinkedList<String>();
      }
      
      // the word to look up in the dictionary
      final String STARTS_WITH = args[1];
      
      // read in the dictionary using a scanner
      final String DICT_NAME = "/cse/course/1020/wordsEn.txt";
      Scanner dictionaryInput = new Scanner(new File(DICT_NAME));
      while (dictionaryInput.hasNextLine())
      {
         String word = dictionaryInput.nextLine().trim();
         dictionary.add(word);
      }
      
      /*
      Count the number of dictionary words that start with STARTS_WITH
      and measure the amount of time required using System.nanoTime()

      Notice that the counting is performed using a for-each loop
      traversal of all of the words in the list
      */
      int numWords = 0;
      long startTime = System.nanoTime();
      for (String word : dictionary)
      {
         if (word.startsWith(STARTS_WITH))
         {
            numWords++;
         }
      }
      long estimatedTime = System.nanoTime() - startTime;
      out.printf("Took %d ns to find %d words starting with %s using a %s%n%n",
                 estimatedTime, numWords, STARTS_WITH, listType);
   }
}

Iterator-based Traversal of List using a for-each Loop

After you are convinced that you understand the program, copy-and-paste it into your editor, save it, and compile it. Run the program several times using both an ArrayList and a LinkedList and observe the relative performance of the two kinds of lists.

Is there any significant difference in speed between ArrayList and LinkedList for iterator-based traversal?

Indexed-based Traversal of List using a for loop

Edit the program replacing the for-each loop with a normal for loop (i.e., use indexed-based traversal); you will need to use the get method to retrieve each word inside the loop.

Run the edited program several times using both an ArrayList and a LinkedList and observe the relative performance of the two kinds of lists.

Is there any significant difference in speed between ArrayList and LinkedList for indexed-based traversal?*

Lesson

The ArrayList version of get supports random access of the element at index i. The index is arbitrary in the sense that it is unpredictable, hence the term random in random access. The common use of the term random access implies O(1) time complexity (i.e., the time to access element i is largely independent of the size of the list).

The LinkedList version of get is sequential access of the element at index i. This means that LinkedList starts at the first element, and proceeds element by element until it reaches element i. Sequential access is O(n) time complexity.

If you need random access, use ArrayList.

Continue to Part 2.