ArrayList相对于LinkedList的优势及性能比较

Question

最近我一直在寻找Java的LinkedLists。经过一些研究，我发现使用LinkedList而不是ArrayList的主要好处是，在包含大量数据的列表中删除/添加元素时，它会更快。因此，使用ArrayList而不总是使用LinkedList会有什么好处呢？

为了比较起见，我编写了这个简单的程序来比较LinkedList和ArrayList之间的运行速度。该程序的概念是，它创建一个长度为n的int数组，并用从integer.min_value到integer.max_value的随机整数填充该数组。

然后，它创建另一个数组，它是第一个数组元素的x%。例如，如果第一数组是[1，2，3，4，5，6，7，8，9，10]，则如果x被设置为50%，则第二数组可以是[2，4，5，9，10]。这将产生一个从原始数组的开始，中间和结束都带有随机元素的数组。

在创建这些数组期间所经过的运行时间不计算在内。然后，程序创建一个LinkedList，将第一个数组中的所有元素添加到这个列表中，并从这个列表中删除第二个数组中的元素。我重复这个过程y次，并使用System.nanoTime()计算平均经过的时间。

我知道我的代码远未优化，但由于它是LinkedList和ArrayList完全相同的代码，只更改正在创建的列表类型，而不预先设置初始化时列表的大小，结果应该不会受到影响，对吗？例如，如果我的错误代码使它的运行速度慢了400%，因为两者都使用相同的代码，结果应该不会受到任何影响，因为理论上两者都慢了400%。

我发现的结果是，ArrayList平均比LinkedList快360%，至少在使用10万整数数组并运行10次同时删除45%元素的情况下是这样。

通过阅读这篇，这篇和这篇StackOverflow文章来比较ArrayList和LinkedList的性能，我了解到，发生这种情况是因为LinkedList为每个节点分配了更多的内存（24字节vs ArrayList上的4字节）。虽然，理论上，LinkedList在数组元素中间添加/删除元素时速度更快，平均只需要O(n/4)步，而List则需要O(n/2)步，但在现实中--至少在我的测试中，以及在上面链接的帖子中执行的测试中--这似乎不是真的。如果是这样，那么问题就反过来了:使用LinkedList而不使用ArrayList有什么好处？只能使用list.iterator()？

下面是我得到的确切结果和我用来得到它们的代码:

It took 53079,970300 ms with LinkedList to run 10 times with an array of 100000 integers removing 45 percent of the elements
The average run time for LinkedList was 5307,997030 ms
It took 14344,833900 ms with normal List to run 10 times with an array of 100000 integers removing 45 percent of the elements
The average run time for normal List was 1434,483390 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

public class LinkedLists {
    public static void main(String[] args) {

        int   timesToRun          = 10;
        int   percentageToRemove  = 45;
        int[] arr                 = getRandomArray(100_000);
        int[] integersToRemoveArr = getIntegersToRemoveArr(percentageToRemove, arr);

        long elapsedTime = 0L;
        long startTime;
        long endTime;

        //LinkedLists
        startTime = System.nanoTime();

        for (int i = 0; i < timesToRun; i++) {
            linkedList(arr, integersToRemoveArr);
        }

        endTime = System.nanoTime();
        elapsedTime += endTime - startTime;
        System.out.printf("It took %f ms with LinkedList to run %d times with an array of %d integers removing %d percent of the elements\n", (endTime - startTime) * 0.000001, timesToRun, arr.length, percentageToRemove);
        System.out.printf("The average run time for LinkedList was %f ms\n", elapsedTime/timesToRun * 0.000001);

        //Force GC - again, not sure I need this, just to be safe
        Runtime.getRuntime().gc();

        //Normal Lists
        elapsedTime = 0L;
        startTime = System.nanoTime();

        for (int i = 0; i < timesToRun; i++) {
            normalList(arr, integersToRemoveArr);
        }

        endTime = System.nanoTime();
        elapsedTime += endTime - startTime;

        System.out.printf("It took %f ms with normal List to run %d times with an array of %d integers removing %d percent of the elements\n", (endTime - startTime) * 0.000001, timesToRun, arr.length, percentageToRemove);
        System.out.printf("The average run time for normal List was %f ms\n", elapsedTime/timesToRun * 0.000001);


    }

    /**
     * Get an array wit X percent of the integers of the providade array
     */
    public static int[] getIntegersToRemoveArr(int percentageToRemove, int[] originalArray) {

        if (percentageToRemove > 100 || percentageToRemove < 0) {
            return new int[]{};
        }

        List<Integer> indexesToRemove = new ArrayList<>();
        while (indexesToRemove.size() < (originalArray.length * (percentageToRemove)/100F)) {
            int x = ThreadLocalRandom.current().nextInt(0, originalArray.length-1);
            indexesToRemove.add(originalArray[x]);
        }

        int[] arr = new int[indexesToRemove.size()];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = indexesToRemove.get(i);
        }

        Arrays.sort(arr);

        return arr;

    }

    public static int[] getRandomArray(int length) {
        if (length < 1) {
            return new int[]{};
        }

        int[] arr = new int[length];

        for (int i = 0; i < length; i++) {
            arr[i] = ThreadLocalRandom.current().nextInt(Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        return arr;
    }

    /**
     * Create a LinkedList from the provided array and remove from the list the elements in integersToRemove
     */
    public static void linkedList(int[] arr, int[] integersToRemove) {
        LinkedList<Integer> list = new LinkedList<>();

        for (int i : arr) {
            list.add(i);

    }
        for (int i : integersToRemove) {
            list.remove((Integer) i);
        }

        //Nulling the element to allow GC to remove it - i'm not sure this is needed since I'm not using
        //this var anywhere, but just to be safe
        list = null;

    }

    /**
     * Create a LinkedList from the provided array and remove from the list the elements in integersToRemove
     */
    public static void normalList(int[] arr, int[] integersToRemove) {
        List<Integer> list = new ArrayList<>();

        for (int i : arr) {
            list.add(i);
        }

        for (int i : integersToRemove) {
            list.remove((Integer) i);
        }

        //Nulling the element to allow GC to remove it - i'm not sure this is needed since I'm not using
        //this var anywhere, but just to be safe
        list = null;

    }
}

Answer 1

好处是您有O(1)Add。尽管ArrayList平均速度更快，但当您add()并需要扩展容量时，它可能会非常慢。对于延迟关键的应用程序，这可能很重要。另外，由于它是一个双重链表，所以前置项比大型ArrayList要快得多，您没有测试过大型ArrayList。