Also available as ListCompare.java

/**
 * Title: ListCompare
 * Description: Creates some different types of Lists and 
 *   times sequences of operations
 *
 * Issues: java has no way of getting at CPU time,
 * so the accuracy of this code relies on
 *    1. short measurements (minimize the chance the process
 *          is interrupted).
 *    2. don't take any single run as gospel, run many times
 *      and look for the most common timings.
 *    3. Elapsed time is an upper bound for CPU time, 
 *       it can report times that are too big (longer than
 *       the code actually takes in CPU time), but it can't
 *       report times too small.
 *
 * @author hollingd@cs.rpi.edu
 */
import java.util.*;

class ListCompare {

  static final int LIST_SIZE=10000;
  static final int MAX_RANDNUM=100000;

  public static void main(String [] args) {

        // runs the tests
        long starttime,diff;  // used for timing

        // buildListAdd test creates a list by adding elements to the
        // end of the list (using add()).

        // try with an ArrayList
        starttime = (new Date()).getTime();
        buildListAdd(new ArrayList());
        diff = (new Date()).getTime() - starttime;
        System.out.println("buildListAdd(ArrayList) Elapsed time was " + diff + " ms.");

        // try with a LinkedList
        starttime = (new Date()).getTime();
        buildListAdd(new LinkedList());
        diff = (new Date()).getTime() - starttime;
        System.out.println("buildListAdd(LinkedList) Elapsed time was " + diff + " ms.");

        // use add to insert new elements randomly (not all at the end).

        // try with an ArrayList
        starttime = (new Date()).getTime();
        buildListInsert(new ArrayList());
        diff = (new Date()).getTime() - starttime;
        System.out.println("buildListInsert(ArrayList) Elapsed time was " + diff + " ms.");

        // try with a LinkedList
        starttime = (new Date()).getTime();
        buildListAdd(new LinkedList());
        diff = (new Date()).getTime() - starttime;
        System.out.println("buildListInsert(LinkedList) Elapsed time was " + diff + " ms.");

        // random access - need a list to start with
        List l1 = new ArrayList();
        buildListAdd(l1);

        // try with an ArrayList
        starttime = (new Date()).getTime();
        randomAccess(l1);
        diff = (new Date()).getTime() - starttime;
        System.out.println("randomAccess(ArrayList) Elapsed time was " + diff + " ms.");


        List l2 = new LinkedList();
        buildListAdd(l2);

        // try with a LinkedList
        starttime = (new Date()).getTime();
        randomAccess(l2);
        diff = (new Date()).getTime() - starttime;
        System.out.println("randomAccess(LinkedList) Elapsed time was " + diff + " ms.");

  }


  // buildList creates a list by calling add 

  public static void buildListAdd(List l) {
        
        // Populate with LIST_SIZE random Integer objects
        Random r = new Random();
        
        for (int i=0;i<LIST_SIZE;i++) {
          l.add( new Integer(r.nextInt(MAX_RANDNUM)));
        }
  }

  // buildListInsert creates a list by inserting elements into the 
  // list at random locations

  public static void buildListInsert(List l) {
        
        // Populate with LIST_SIZE random Integer objects
        Random r = new Random();
        
        l.add( new Integer(r.nextInt(MAX_RANDNUM)));
        for (int i=1;i<LIST_SIZE;i++) {
          l.add( r.nextInt(l.size()),new Integer(r.nextInt(MAX_RANDNUM)));
        }
  }


  // randomAccess accesses list elements randomly
  public static void randomAccess(List l) {
        
        Random r = new Random();

        for (int i=0;i<LIST_SIZE;i++) {
           l.get(r.nextInt(LIST_SIZE));
        }
  }

}