Home CPSC 340

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

To time a program on the command line, simply prefix the command with the word time. This will run the command you give and report how long it took to execute. For example:

$ time java Program
real    0m18.625s
user    0m18.520s
sys     0m0.052s

The time command outputs the time in three categories. The one we care about is the "real" time, which is the first row. This refers to how much actual time has elapsed during execution.

"User" and "sys" time refer to how much time was spent executing "user" code vs. "system code. When a program makes calls to the operating system (such as to print to the terminal or allocate memory) that is counted separately. Also the user and sys time could be more than real time if we had used multiple threads, since it counts time used on a CPU.

So look at the "real" time when making these comparisons.


 

Details

  1. Start by writing a program which creates an ArrayList of Integer. It should then add 5,000,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.
  2. 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.
  3. Next, change the program so that it adds 500,000 numbers to the start of the list instead. Repeat the experiment timing how long the program takes now.
  4. 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.

 

Heap Size

It's possible that trying to make a list of the 5 million numbers will be too much for your Java VM. If you get an error like this:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Then you will need to increase the maximum size of the heap. That can be done by passing the -Xmx flag to the java command, followed by the size you want. For example, passing a maximum of 4 gigabytes should be plenty. Run your program like this to achieve that:

$ java -Xmx4g ProgramName

 

Testing

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

Data StructureNSideTime
ArrayList 5,000,000End---
LinkedList5,000,000End---
ArrayList 500,000Start---
LinkedList500,000Start---

Also, answer the following questions:

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

 

Submitting

When you're finished, email the table (which can just be in the text of an email), and your answers to the three questions to ifinlay@umw.edu.

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.