Lab 2: Linked Lists vs. Array Lists

Objective

To compare the performance of adding to Java's Linked Lists vs. Array Lists

Task

For this Lab, you will be writing code to compare the performance of adding data to Java's built-in LinkedList and ArrayList classes. We will be adding data to the beginning and end of both of these data structures and timing how long it takes to run these programs.

Timing a Program

In order to test how long a program takes to run, we will see what time it is at the very start of the program, and then again at the very end. We will then subtract these two values which gives us the amount of time that has elapsed.

We can get a time reading with the System.nanoTime method:


long startTime = System.nanoTime();

This returns a value in nano-second units, so it should be put in a long variable. That should be done at the very start of main, before anything else. Then at the end of the program, we take another time reading:


long endTime = System.nanoTime();

We can then compute the difference between them. We will also convert to milliseconds by dividing by 1000000:


long elapsedMS = (endTime - startTime) / 1000000;
System.out.println("Elapsed time = " + elapsedMS + " milliseconds.");

Details

Start by writing a program which creates an ArrayList of Integer. It should then add 500,000 numbers to the end of the list. You can do this using a for loop and adding the index to the list with the add method each time through.
Time this program and see how long it takes, recording the number. Do three tests and average the results to improve the accuracy of the test.
Next, change the program so that it adds all of the numbers to the start of the list instead. Repeat the experiment timing how long the program takes now.
Next, do the same two experiments again, but this time using Java's built-in LinkedList class instead of ArrayList (make sure not to use our version). Record the time taken to run these two versions of the program.

Testing

For this lab, you can fill out the following table of times:

Data Structure	Side	Time
ArrayList	End	---
ArrayList	Start	---
LinkedList	End	---
LinkedList	Start	---

Also, answer the following questions:

Which data structure is better for adding to the end?
Which data structure is better for adding to the start?
Are these small differences or big ones?

Submitting

When you're finished, submit the table, along with your answers to the three questions on Canvas. You can either just enter text for your submission, or upload a document.