Removing Elements

The following program should allow the user to remove words from the dictionary that are longer than N letters in length. For example:

java Remove array 12
Took 267896079 ns to remove 7943 words longer than 12 using a ArrayList

java Remove array 5
Took 3253874392 ns to remove 98539 words longer than 5 using a ArrayList

java Remove array 0
Took 3869650883 ns to remove 109583 words longer than 0 using a ArrayList

Notice that the last example above effectively removes all of the words from the dictionary.

Copy-and-paste the program into your editor.

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

public class Remove
{
   public static void main(String[] args) throws IOException
   {
      PrintStream out = System.out;
      
      if (args.length != 2)
      {
         out.println("Usage: java Remove <list-type> N");
         out.println("where <list-type> is linked or array");
         out.println("and N is the maximum word length to keep");
         System.exit(1);
      }
      
      // create the dictionary list
      String listType = "ArrayList";
      List<String> dictionary = new ArrayList<String>();
      if (args[0].equals("linked"))
      {
         listType = "LinkedList";
         dictionary = new LinkedList<String>();
      }
      
      // maximum word length
      final int N = Integer.parseInt(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);
      }

      int nRemoved = 0;
      long startTime = System.nanoTime();
      /*
         YOUR LOOP GOES HERE   
      */
      long estimatedTime = System.nanoTime() - startTime;
      out.printf("Took %d ns to remove %d words longer than %d using a %s%n%n",
                 estimatedTime, nRemoved, N, listType);
      
   }
}

Using Iterator

It is very difficult to safely and correctly traverse a collection and selectively remove elements. For example, you might think to use indexed traversal to visit each element and then use the List method remove to selectively remove elements:

      for (int i = 0; i < dictionary.size(); i++)
      {
         String word = dictionary.get(i);
         if (word.length() > N)
         {
            dictionary.remove(i);
            nRemoved++;
         }
      }

Try inserting this code into the program and see how many words it removes for N = 5 (a correct loop would remove 98,539 words):

java Remove array 5

The safest way to traverse a collection and selectively remove elements is to use an iterator. Read the following brief tutorial on using an iterator. and complete the Remove program.

Is there any significant difference in speed between ArrayList and LinkedList for removing elements?

Lesson

Removing (or inserting) an element from an array or an ArrayList has O(n) time complexity. The same operations for LinkedList have O(1) time complexity.

If you find that you are frequently traversing a collection to selectively remove or insert elements, you should consider using a LinkedList.

Submit

Submit your program using the command:

submit 1020 L10 Remove.java

All done.