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 gives you a nice overview. For reliable benchmarks, you should use a proper tool such as JMH, because there are so many pitfalls that can make a simple "for-loop in main" benchmark give undesireable results. — Mick Mnemonic
– Mick Mnemonic, Commented Apr 12, 2015 at 0: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
– Turing85, Commented Apr 12, 2015 at 0: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
– Mick Mnemonic, Commented Apr 12, 2015 at 0:57
It is also important to understand that asking the system for time (via System.currentTimeMillis() or System.nanoTime()) is not cheap. — Mick Mnemonic
– Mick Mnemonic, Commented Apr 12, 2015 at 1:06

SmashMaster · Accepted Answer · 2015-04-12 03:29:01Z

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.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related