Java ArrayList与LinkedList的性能，仅与创建/插入和排序有关

Question

请考虑以下代码：

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();
    }
}

其中Pair是自定义定义的数据结构。

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

上述程序的输出：Creating ArrayList:Time Elapsed=0.885秒

创建链接列表：已用时间 = 9.617 秒

排序数组列表：所用时间=0.128秒

对链接列表进行排序：已用时间 = 0.351 秒

我有点困惑，因为直觉上，LinkedList的创建应该比ArrayList更好。

对于排序，这是意料之中的，正如它在api：https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html中所说，Collections.sort将列表转储到ArrayList，对其进行排序，并将其转换回原始列表类型（对此不确定）

如果原始列表类型是ArrayList，我想可能会有优化。

Answer 1

这将是特定于实现的，取决于ArrayList在您的平台上如何增长...但在大多数平台上，每当达到其容量时，它的大小就会增加1.5倍。

下面是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);
}

如果您将一千万个对象添加到一个空的ArrayList中，这个方法将被调用36次，ArrayList的默认初始容量是10。我在grow()和Arrays.copyOf()上进行了一些分析，它们非常快，即使对于大型数组也是如此。

另一方面，LinkedList需要为添加到它的每个元素分配一个新的Node对象——一千万次。这就是为什么LinkedList在这种情况下比较慢的原因。当您需要在列表的开头或中间插入或删除元素时，速度会快得多。