Home > IB Computer Science 2017 > java.util.ArrayList vs java.util.LinkedList

java.util.ArrayList vs java.util.LinkedList

This is my answer to the task I set you the other day. It prints out the number of nanoseconds that two different types of operation take on each of the two different data structures.

Each list was initialized with 1,000,000 int elements and the output shows that it took over 400 times longer to access the middle of the LinkedList than to access the middle of the ArrayList, but over 40 times longer to add an element to the front of the ArrayList than to the front of the LinkedList.

We know that inserting at the front of an array is problematic because every element has to shift up one to make room for the new element, but it is less obvious why arrays support direct access so well.

The reason is twofold:

  • Every element in an array is the same size
  • The elements are contiguous in memory

This means that if we know the address of the base element of the array, and we know the size in bytes of each element, then we can calculate the address of the start of the nth element as [(base address) + n * (element size)]. Knowledge of the address of an object in RAM allows us to jump straight to that object (this is what the address bus does).

package listtypesdemo;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

/**
 *
 * @author robertsonj
 */
public class ListTypesDemo {

    /**
     * @param args the command line arguments
     */
    ArrayList<Integer> aList = new ArrayList();
    LinkedList<Integer> lList = new LinkedList();

    public static void main(String[] args) {
        ListTypesDemo demo = new ListTypesDemo();
        final int ELEMENTS = 10000000;
        final int UPPER_BOUND = 100;
        demo.init(ELEMENTS, UPPER_BOUND);

        long start = 0, stop = 0;
        String msg = "";
        for (int i = 0; i < 4; i++) {
            start = System.nanoTime();
            // make call to time-consuming function here
            switch (i) {
                case 0:
                    msg = "Accessing middle of ArrayList...";
                    demo.aList.get(ELEMENTS / 2);
                    break;
                case 1:
                    msg = "Accessing middle of LinkedList...";
                    demo.lList.get(ELEMENTS / 2);
                    break;
                case 2:
                    msg = "Inserting at start of ArrayList...";
                    demo.aList.add(0, 0);
                    break;
                case 3:
                    msg = "Inserting at start of LinkedList...";
                    demo.lList.add(0, 0);
                    break;
                default:
                    msg = "Assertion failure.";
            }
            stop = System.nanoTime();
            System.out.println(msg);
            System.out.println(stop - start);
        }
    }

    void init(int ELEMENTS, int UPPER_BOUND) {
        Random r = new Random();
        for (int i = 0; i < ELEMENTS; i++) {
            aList.add(r.nextInt(UPPER_BOUND));
            lList.add(r.nextInt(UPPER_BOUND));
        }
    }
}

This is the output it produces:

run:
Accessing middle of ArrayList...
7222
Accessing middle of LinkedList...
2943557
Inserting at start of ArrayList...
754515
Inserting at start of LinkedList...
16724
BUILD SUCCESSFUL (total time: 1 second)
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s