Lab 7: Comparing Data Structures

Due Date and Submission Requirements

The goal of this lab is:

This assignment will be slightly different than other assignments we’ve done. In this lab, you will conduct an experiment comparing the running time of adding elements to an ArrayList, LinkedList, TreeSet, and HashSet. This lab should be pretty easy (do not overthink it).

Directions

You will create one class for this lab: Lab7Demo.java. All your code can go inside this class (it can all go insde the main method if you'd really like). You do not need to define any other classes.

You can calculate the running time (in milliseconds) for some operation by using the following Java code:

long start_time = System.nanoTime();
// code for inserting 100000 random values go here...
long end_time = System.nanoTime();
long elapsed_time = (end_time - start_time);
double milliseconds = elapsed_time / 1000000.0;


You will be writing code that adds 100,000 random numbers (with random.nextInt()) to four different data structures: ArrayList, LinkedList, TreeSet (a set that is represented by a BST), and HashSet.

Before you start writing code, you should make a prediction about about which data structure will have the fastest running time, and which data structure will have the slowest running time. You don't need to write this down anywhere... just do it in your head.

First write some code that will add 100,000 random numbers (with random.nextInt()) to an ArrayList using the .add() method. After the for loop has finished, you should print out the total elapsed time.

Next, write some code that will add 100,000 random numbers with random.nextInt()) to a LinkedList using the .add() method. After the for loop has finished, you should print out the total elapsed time.

Next, write some code that will add 100,000 random numbers (with random.nextInt()) to a TreeSet using the .add() method. Creating a TreeSet is just like how you create a linked list or array list. After the for loop has finished, you should print out the total elapsed time.

Next, write some code that will add 100,000 random numbers (with random.nextInt()) to a HashSet using the .add() method. When you make the HashSet, give it an initial size of 150000 ( HashSet hash = new HashSet<>(150000); ). This will eliminate the amount of resizing+rehashing the hash table will need to do. After the for loop has finished, you should print out the total elapsed time.

After doing this, you should have four values printed out: the time (in milliseconds) it took to add 100000 numbers into an ArrayList, LinkedList, TreeSet, and HashSet. You should run your program several times to see how your results change.

Using your knowledge of the running times of these operations, do the results from your experiment make sense? If they don't, that is fine . Your code is probably still correct. There are things happening behind the scenes that we will discuss after spring break.

Required Output

When you run your program, it should look similar to this screenshot. I don't want to spoil the results of the experiement, so I censored out the values in the screenshot.

Grading (10 points)

NOTE: If your code does not compile, correctness cannot be verified, and you won’t receive any points for your code. Turn in code that compiles!