ArrayList vs LinkedList

I’ve always wanted to really check when we should use which list implementation in Java. You know theory: ArrayList should be faster to get element by position while LinkedList should be much faster to remove and add elements somewhere in the middle. But how does it look in the real world? I’ve done some quick benchmark and here are results (it’s time so smaller is better):

Add Iterate Remove last Remove first Random get Random insert
ArrayList 0001.00 0000.00 0004.00 0001.00 0006.00 2937.00
LinkedList 0015.00 0000.00 0003.00 0000.00 7013.00 36215.00
Random remove Contains Middle get Middle insert Middle remove Middle contains
ArrayList 0558.00 7722.00 0007.00 1962.00 0535.00 7042.00
LinkedList 5101.00 18342.00 11774.00 20428.00 5246.00 17053.00
Insert before
ArrayList 3516.00
LinkedList 0023.00

Just see these results! It looks like it’s never worth using LikedList. Tests were tun on 100000 (hundred thousand) elements list and adding 100000 next if it was needed. Every test was run 10 times and average value was taken.

Add, iterate, remove last, remove first – these don’t really matter. Use what you like. But the rest? It looks horrible for LinkedList. Especially operations that should be faster: random insert for example… more than 10 times slower! What? This totally kills LinkedList as collection to keep anything. It’s not faster in some operations and much, much slower in rest. It’s so slow i can’t really believe it. It looks like System.arraycopy is really doing good work.

Everything was run with -XX:CompileThreshold=1 and few warmup passes, so everything should be compiled before benchmark and compilation shouldn’t change the results.
I’ve added middle actions to avoid randomizer overhead, but it does not look like it could do any difference with so big performance differences.

You can run it for yourself (but be warned it takes hours rather that minutes with 100000 elements). Here’s the source code:

package com.wordpress.jdevel.benchmark;

import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.EnumMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.logging.Logger;

/**
 * Remember to run it with "-XX:CompileThreshold=1" so all code is compiled before benchmark
 * @author Marek Piechut
 */
public class ListBenchmark {

    private static volatile int operations;
    private static volatile int RUNS = 10;
    private static final NumberFormat NF = new DecimalFormat("0000.00");

    enum STEP {

        ADD(add), ITERATE(iterate), REM_LAST(rem_last), REM_FIRST(rem_first),
        RANDOM_GET(random_get), RANDOM_INSERT(random_insert), RANDOM_REMOVE(random_remove), CONTAINS(contains),
        MIDDLE_GET(middle_get), MIDDLE_INSERT(middle_insert), MIDDLE_REM(middle_remove), MIDDLE_CONTAINS(middle_contains),
        INSERT_BEFORE(insert_before);
        //
        private final Operation operation;

        private STEP(Operation operation) {
            this.operation = operation;
        }

        public Operation getOperation() {
            return operation;
        }
    }

    public static void main(String[] args)
            throws Exception {
        //Make sure code is compiled before benchmark
        operations = 100;
        for (int i = 0; i < 5; i++) {
            for (Class class1 : new Class[]{ArrayList.class, LinkedList.class}) {
                run(class1);
            }
        }

        //Now let's benchmark
        operations = 100000;
        Map<STEP, List<Long>> array = run(ArrayList.class);
        Map<STEP, List<Long>> linked = run(LinkedList.class);

        print("AL", array);
        print("LL", linked);
    }

    private static void print(String label, Map<STEP, List<Long>> map) {
        StringBuilder sb = new StringBuilder(label);
        sb.append(": ");
        for (STEP step : map.keySet()) {
            List<Long> times = map.get(step);
            long sum = 0;
            for (Long time : times) {
                sum += time;
            }
            double med = sum / times.size();
            sb.append(step).append(' ').append(NF.format(med)).append('\t');
        }
        System.out.println(sb);
    }

    public static Map<STEP, List<Long>> run(Class<? extends List> listClass)
            throws Exception {
        Map<STEP, List<Long>> resultsMap = new EnumMap<STEP, List<Long>>(STEP.class);
        //Now let's benchmark
        for (int i = 0; i < RUNS; i++) {
            for (STEP step : STEP.values()) {
                long time = test(step, listClass.newInstance());
                if (resultsMap != null) {
                    List<Long> results = resultsMap.get(step);
                    if (results == null) {
                        results = new ArrayList<Long>(RUNS);
                        resultsMap.put(step, results);
                    }

                    results.add(time);
                }
            }
        }

        return resultsMap;
    }

    public static long test(STEP step, List l) {
        fill(l);
        Operation operation = step.getOperation();
        long startTime = System.currentTimeMillis();
        boolean result = operation.operate(l);
        long endTime = System.currentTimeMillis();

        long time = endTime - startTime;
        return time;
    }

    private static final void fill(List l) {
        add.operate(l);
    }

    static interface Operation {

        boolean operate(List l);
    }
    private static final Operation add = new Operation() {

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                //Avoid integer cache
                Integer value = new Integer(i);
                l.add(value);
            }

            return l != null;
        }
    };
    private static final Operation iterate = new Operation() {

        public boolean operate(List l) {
            for (Iterator it = l.iterator(); it.hasNext();) {
                Object object = it.next();
            }

            return l != null;
        }
    };
    private static final Operation rem_last = new Operation() {

        public boolean operate(List l) {
            for (int i = operations - 1; i >= 0; i--) {
                l.remove(i);
            }

            return l != null;
        }
    };
    private static final Operation rem_first = new Operation() {

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                l.remove(l.size() - 1);
            }

            return l != null;
        }
    };
    private static final Operation random_get = new Operation() {

        private final Random random = new Random();

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = random.nextInt(operations);
                Object get = l.get(nextInt);
                get.toString();
            }
            return l != null;
        }
    };
    private static final Operation random_insert = new Operation() {

        private final Random random = new Random();

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = random.nextInt(operations);
                Integer integer = new Integer(nextInt);
                l.add(nextInt, integer);
            }
            return l != null;
        }
    };
    private static final Operation random_remove = new Operation() {

        private final Random random = new Random();

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = random.nextInt(l.size());
                l.remove(nextInt);
            }
            return l != null;
        }
    };
    private static final Operation contains = new Operation() {

        private final Random random = new Random();

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = random.nextInt(operations);
                boolean c = l.contains(nextInt);
            }
            return l != null;
        }
    };
    private static final Operation middle_get = new Operation() {

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = l.size() / 2;
                Object get = l.get(nextInt);
                get.toString();
            }
            return l != null;
        }
    };
    private static final Operation middle_insert = new Operation() {

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = l.size() / 2;
                Integer integer = new Integer(nextInt);
                l.add(nextInt, integer);
            }
            return l != null;
        }
    };
    private static final Operation middle_remove = new Operation() {

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = l.size() / 2;
                l.remove(nextInt);
            }
            return l != null;
        }
    };
    private static final Operation middle_contains = new Operation() {

        public boolean operate(List l) {
            for (int i = 0; i < operations; i++) {
                int nextInt = l.size() / 2;
                boolean c = l.contains(nextInt);
            }
            return l != null;
        }
    };

    private static final Operation insert_before = new Operation() {

        private final Random random = new Random();

        @Override
        public boolean operate(List l) {
            for (ListIterator it = l.listIterator(); it.hasNext();) {
                it.next();
                it.add(random.nextInt(l.size()));
            }
            return l != null;
        }
    };
}

What’s the conclusion? For me: always use ArrayList. It’s faster, toArray() takes no time as only copy of internal array is returned (System.arraycopy again).
The only issue could be with memory footprint. But haven’t tested it, yet…

Update:

I’ve done a one more quick test with ListIterator (thanks Iain Shepherd for pointing this out) and more LinkedList way of doing things and it’s where LinkedList really shines. Check “Insert before” in table for results and insert_before Operation in code. What this test exactly does is that it inserts one random Integer before each object in list using ListIterator.add method. So if you’re modifying list during iteration LinkedList should be much faster, for other use cases I would still stick to ArrayList.

Advertisements

8 Responses to ArrayList vs LinkedList

  1. deepa says:

    What was the size of data you tested upon? Results vary with growing size.

  2. Eugene says:

    Regarding unintuitive results on insert/remove – since you’re using your list as an array it’s no wonder that closest to array implementation wins Linked lists are typically searched by element reference/value not by the index.

    • Marek Piechut says:

      But how do you search by reference using linked list if not by traversing all elements from beginning or end (doubly linked list)? It’s quite similar to insert by position. If you could get LinkedList internal Entry object for element you want to insert after or remove, then it should be much faster, but there is no way you can get it with LinkedList API. Do you have some other idea how to achieve something like this in Java?

  3. Iain Shepherd says:

    Presumably LinkedList can win in rare situations, where you want to examine a large list front-to-back, and insert or remove as you go. And assuming you need to do this several times (so as to amortise the high cost of populating it in the first place).

    I guess you are aware of ListIterator? I just wondered after reading your reply to Eugene.

    • Marek Piechut says:

      Hi.

      Hmm you’re right. I’ll rework this benchmark with ListIterator if i have code still lying somewhere and check once again.

    • Marek Piechut says:

      Updated benchmark and post. In “modify while iterating” usage pattern LinkedList really shines. Thanks Iain for pointing this out.

  4. Pingback: JavaPins

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

%d bloggers like this: