Performance on Java ArrayList vs LinkedList, pertaining to only Creation/Insertion and sorting

Question

Consider the following code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class testSortingSpeed {
    public static final int TOTAL_NUMBER = 10000000;

    public static void main(String[] args) {
        System.out.println("Creating ArrayList:");
        List<Pair<Integer, Integer>> a = new ArrayList<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < TOTAL_NUMBER; i++) {
            Pair<Integer, Integer> p = new Pair<>(
                (int ) Math.random() * TOTAL_NUMBER,
                (int ) Math.random() * TOTAL_NUMBER);
            a.add(p);
        }
        long end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();

        System.out.println("Creating LinkedList:");
        List<Pair<Integer, Integer>> b = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < TOTAL_NUMBER; i++) {
            Pair<Integer, Integer> p = new Pair<>(
                (int ) Math.random() * TOTAL_NUMBER,
                (int ) Math.random() * TOTAL_NUMBER);
            b.add(p);
        }
        end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();

        System.out.println("Sorting ArrayList:");
        start = System.currentTimeMillis();
        Collections.sort(a, Pair.LEXICOGRAPHIC_ORDER);
        end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();

        System.out.println("Sorting LinkedList:");
        start = System.currentTimeMillis();
        Collections.sort(b, Pair.LEXICOGRAPHIC_ORDER);
        end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();
    }
}

where Pair is a custom defined data structure.

Pair<F, S> { F first; S second; }

The output of the above program: Creating ArrayList: Time Elapsed = 0.885 seconds

Creating LinkedList: Time Elapsed = 9.617 seconds

Sorting ArrayList: Time Elapsed = 0.128 seconds

Sorting LinkedList: Time Elapsed = 0.351 seconds

I am a bit baffled, cos intuitively, LinkedList creation should be better than ArrayList.

For sorting, that's kinda expected, as it says in api: https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html that Collections.sort dumps the list to an ArrayList, sort it, and convert it back to original list type (not sure about this)

and I guess there is probably optimization if the original list type is ArrayList.

For comparing the complexity of operations in different `List` implementations, [this thread](http://stackoverflow.com/questions/1713144/list-implementations-does-linkedlist-really-perform-so-poorly-vs-arraylist-and) gives you a nice overview. For reliable benchmarks, you should use a proper tool such as [JMH](http://openjdk.java.net/projects/code-tools/jmh/), because there are so many [pitfalls](http://www.oracle.com/technetwork/articles/java/architect-benchmarking-2266277.html) that can make a simple "for-loop in `main`" benchmark give undesireable results. — Mick Mnemonic, Apr 12 '15 at 00:45
Also it may be possible (not totally sure) that the JRE unrolls the loop and therefore can create an `ArrayList` of appropiate size from the get-go, which might explain the difference in performance. Keep in mind, that a `LinkedList` needs some kind of `Node` object to wrap around the value. You do not need this for an `ArrayList`. — Turing85, Apr 12 '15 at 00:54
Also, the reason why list sorting is so fast may be the _dead-code elimination_ done by the HotSpot VM (see the benchmarking pitfalls link for more details); you're not using the sorted lists for anything. — Mick Mnemonic, Apr 12 '15 at 00:57
It is also important to understand that asking the system for time (via `System.currentTimeMillis()` or `System.nanoTime()`) [is not cheap](http://shipilev.net/blog/2014/nanotrusting-nanotime/). — Mick Mnemonic, Apr 12 '15 at 01:06

SmashMaster · Answer 1 · 2015-04-12T03:29:01.290

This will be implementation specific, depending on how ArrayList grows on your platform... But on most platforms, it multiplies its size by a factor of 1.5 every time it's capacity is reached.

Here's the code from JDK 1.8:

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

This method will be called 36 times if you're adding ten million objects into an empty ArrayList, which has a default initial capacity of 10. I've done some profiling on grow() and Arrays.copyOf(), and they're very fast, even for large arrays.

LinkedList, on the other hand, needs to allocate a new Node object for every element added to it--ten million times. That's why LinkedList is slower in this case. It's much faster when you need to insert or remove elements somewhere near the beginning or middle of the list.

Performance on Java ArrayList vs LinkedList, pertaining to only Creation/Insertion and sorting

1 Answers1

Linked