Title: Performance List Interface
Course: CPS 261: Advanced Java Concepts ~ DL & MM MASTER

Performance: List Interface

If we have multiple data structures that implement the List interface, how do we decide which data structure to use (ArrayList, LinkedList, Vector).

Although each of these classes implement the same interface, some of the methods can execute poorly for some data structures.

To demonstrate this, I will run a few different tests and compare ArrayList with LinkedList.

For these tests, we will be using the following utility class:

Timer.java

Iteration Performance




import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class IteratePerformance {


    Integer nextNum()
    {
        return (int)(Math.random() * 1000);
    }
    void endBuild(List<Integer> list, int n)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        for (int i=0; i < n; i++)
        {
            list.add(nextNum());
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }
    void iterate(List<Integer> list)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        Iterator<Integer> iter = list.iterator();
        while(iter.hasNext())
        {
            Integer i2 = iter.next();
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    void forLoop(List<Integer> list)
    {
        Timer timeIt = new Timer();
        timeIt.start();
        int len = list.size();

        for (int i=0; i < len; i++)
        {
            Integer i2 = list.get(i); // This is a bad call to make for LinkedList
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    public static void main(String[] args) {
        System.out.println("Enter in N");
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();

        IteratePerformance ipc = new IteratePerformance();

        List<Integer> list = new LinkedList<Integer>();
       // Re-run this with ArrayList


        System.out.println("endBuild");
        ipc.endBuild(list, n);

        System.out.println("iterate");
        ipc.iterate(list);

        System.out.println("forLoop");
        ipc.forLoop(list);

        keyboard.close();

    }

}



Timings for LinkedList

N | 100,000 | 200,000 | 400,000
Iterate | 0 | 0.03 | 0.09
For Loop | 5.5 | 33 | 179

Timings for ArrayList

N | 200,000 | 400,000 | 4,000,000
Iterate | 0 | 0.01 | 0.03
For Loop | 0 | 0 | 0.02

Why is the For Loop so bad for LinkedList?

For fun, run the Iteration ArrayList N upto 16000000.

Adding Data to a List


import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class InsertionPerformanceComparisons {

    Integer nextNum()
    {
        return (int)(Math.random() * 1000);
    }

    void frontBuild(List<Integer> list, int n)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        for (int i=0; i < n; i++)
        {
            list.add(0, nextNum());
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }
    void middleBuild(List<Integer> list, int n)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        for (int i=0; i < n; i++)
        {
            list.add(i/2, nextNum());
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }

    void endBuild(List<Integer> list, int n)
    {
        Timer timeIt = new Timer();
        timeIt.start();

        for (int i=0; i < n; i++)
        {
            list.add(list.size() , nextNum());
        }
        timeIt.stop();
        System.out.printf("time=%.2f seconds%n", timeIt.time() );
    }





    public static void main(String[] args) {

        System.out.println("Enter in N ");
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();

        InsertionPerformanceComparisons ipc = new InsertionPerformanceComparisons();

        List<Integer> list = new LinkedList<Integer>();
        // Also try ArrayList


        System.out.println("endBuild");
        ipc.endBuild(list, n);


        list.clear();
        System.out.println("frontBuild");
        ipc.frontBuild( list, n);

        list.clear();
        System.out.println("middleBuild");
        ipc.middleBuild( list, n);

        keyboard.close();
    }

}



Timings for LinkedList

N | 100,000 | 200,000 | 400,000 | 800,000
Insert at End | 0.01 | 0.03 | 0.11 | 0.23
Insert at Beginning | 0.01 | 0.03 | 0.11 | 0.11
Insert at Middle | 11 | 60 | 237 | 1728

Timings for ArrayList

N | 100,000 | 200,000 | 400,000 | 800,000
Insert at End | 0.01 | 0.02 | 0.04 | 0.11
Insert at Beginning | 1.21 | 5.3 | 21.7 | 87
Insert at Middle | 0.54 | 2.4 | 10.6 | 43

Last Updated:

July 22, 2014 9:54 PM