likes
comments
collection
share

性能对决：LinkedList vs ArrayList，结果出乎意料

作者站长头像
站长
· 阅读数 2

jdk版本：1.8

在工作中经常使用 LinkedList 和 ArrayList，但是什么情况下该使用 LinkedList，什么情况下该使用 ArrayList；由于LinkedList底层存储是链表结构，ArrayList 底层是数组结构。通常建议是ArrayList适合随机访问，LinkedList适合插入和删除操作，真的是这样的吗，通过单机测试发现这个建议不是很合理，以下是我测试LinkedList和 ArrayList 的 内存容量占用、get耗时、add耗时、remove耗时、迭代遍历耗时对比结果。

内存占用分析

这里使用了lucene工具进行计算集合内存占用。

lucene jar包引入

<dependencies>
    <dependency>
        <groupId>org.apache.lucene</groupId>
        <artifactId>lucene-core</artifactId>
        <version>4.0.0</version>
    </dependency>
    <dependency>
        <groupId>org.apache.commons</groupId>
        <artifactId>commons-lang3</artifactId>
        <version>3.12.0</version>
    </dependency>

内存占用分析Java代码

List<Object> list = new LinkedList<>();
List<Object> arrayList = new ArrayList<>();

int size = 1;
for (int i = 0; i < 23; i++) {
    // 指数级增加容量
    size = size * 2;
    for (int j = 0; j < size; j++) {
        list.add(new Object());
        arrayList.add(new Object());
    }
    System.out.println("capacity size:" + size + ",[LinkedList, ArrayList]:[" + RamUsageEstimator.humanSizeOf(list) 
            + "," + RamUsageEstimator.humanSizeOf(arrayList) + "]");
    list.clear();
    arrayList.clear();
}

运行结果：

性能对决：LinkedList vs ArrayList，结果出乎意料 用二维图展示：

性能对决：LinkedList vs ArrayList，结果出乎意料

小结论

LinkedList 因为是链表结构，每个节点都需要封装成Node里面，自然占用更多的内存空间，从上面数据可以看出LinkedList占用的存储空间几乎是ArrayList的两倍；

get耗时分析

这个没什么悬念，LinkedList 每次get都是从链表头开始寻找，而ArrayList底层是数组，可直接计算出存储位置，所以LinkedList get耗时远超ArrayList。

get耗时分析Java代码

List<Integer> list = new LinkedList<>();
List<Integer> arrayList = new ArrayList<>();

int size = 1;
for (int j = 1; j < 18; j++) {
    size = size * 2;
    for (int i = 0; i < size; i++) {
        list.add(i);
    }

    long listBegin = System.nanoTime();
    for (int i = 0; i < size; i++) {
        list.get(i);
    }
    double listCost = (System.nanoTime() - listBegin) / 1000000.0;
    System.out.print("lists size: " + size + "; get cost time[LinkedList, ArrayList]:[" + listCost);
    list.clear();

    for (int i = 0; i < size; i++) {
        arrayList.add(i);
    }
    long arrayListBegin = System.nanoTime();
    for (int i = 0; i < size; i++) {
        arrayList.get(i);
    }
    double arrayCost = (System.nanoTime() - arrayListBegin) / 1000000.0;
    System.out.println("ms, " + arrayCost + "ms]");
    arrayList.clear();
}

性能对决：LinkedList vs ArrayList，结果出乎意料 用二维图展示：

性能对决：LinkedList vs ArrayList，结果出乎意料

小结论

LinkedList get 复杂度是o(n), ArrayList 是o(1)。

add耗时分析

LinkedList add是在链表尾部追加；ArrayList 是在数字最后追加，如果超过容量阈值存在扩容；表象看LinkedList add会更快些，因为不需要扩容，实际测试结果却不是这样。

add耗时分析Java代码

List<Integer> list = new LinkedList<>();
List<Integer> arrayList = new ArrayList<>();

int size = 1;

for (int j = 1; j < 11; j++) {
    size = size * 5;
    long listBegin = System.nanoTime();
    for (int i = 0; i < size; i++) {
        list.add(i);
    }
    System.out.print("lists size: " + size + "; add cost time[LinkedList, ArrayList]:[" + (System.nanoTime() - listBegin) / 1000000.0);
    list.clear();

    long arrayListBegin = System.nanoTime();
    for (int i = 0; i < size; i++) {
        arrayList.add(i);
    }
    System.out.println("ms, " + (System.nanoTime() - arrayListBegin) / 1000000.0 + "ms]");
    arrayList.clear();
}

性能对决：LinkedList vs ArrayList，结果出乎意料 用二维图展示：

性能对决：LinkedList vs ArrayList，结果出乎意料

小结论

随着集合容量的增加，LinkedList add累计耗时直线上升，ArrayList add累计耗时上升很慢；LinkedList 慢的原因应该是每次add一个值都需要封装成Node然后追加到链表尾部，每次封装Node（实例化Node对象）的耗时不容小觑；ArrayList add 不需要封装，影响耗时的只有扩容，而每次扩容都是调用底层System.arraycopy 数组拷贝，这个拷贝函数内存复制执行很快，而且每次扩容int newCapacity = oldCapacity + (oldCapacity >> 1); 为原容量的1.5倍，所以随着容量增加其实扩容不了几次，这也是ArrayList add速度快的原因。

remove耗时分析

remove过程为 找到需要移除值位置，然后删除；LinkedList 找到位置后只需要操作指针便可，而 ArrayList 找到所在位置后需要使用System.arraycopy 移除数组所在位置值。

remove耗时分析Java代码

List<Integer> list = new LinkedList<>();
List<Integer> arrayList = new ArrayList<>();

int size = 1;

for (int j = 1; j < 16; j++) {
    size = size * 2;
    // 集合LinkedList初始化
    for (int i = 0; i < size; i++) {
        list.add(i);
    }

    long listBegin = System.nanoTime();
    // 开始随机移除
    for (int i = 0; i < size; i++) {
        list.remove(Integer.valueOf(getRandomValue(size)));
    }
    double listCost = (System.nanoTime() - listBegin) / 1000000.0;
    System.out.print("lists size: " + size + "; random remove time[LinkedList, ArrayList]:[" + listCost);
    list.clear();
    
    // 集合ArrayList初始化
    for (int i = 0; i < size; i++) {
        arrayList.add(i);
    }
    long arrayListBegin = System.nanoTime();
    // 开始随机移除
    for (int i = 0; i < size; i++) {
        arrayList.remove(Integer.valueOf(getRandomValue(size)));
    }
    double arrayCost = (System.nanoTime() - arrayListBegin) / 1000000.0;
    System.out.println("ms, " + arrayCost + "ms]");
    arrayList.clear();
}

性能对决：LinkedList vs ArrayList，结果出乎意料 用二维图展示： 性能对决：LinkedList vs ArrayList，结果出乎意料

小结论

测试运行了10次以上，二维图变化不大，可信度很高。

从二维图可以看出 ArrayList remove 耗时几乎比 LinkedList 快7倍；之所以这么快应该是ArrayList遍历比LinkedList遍历要更快，而且 ArrayList 使用System.arraycopy 移除效率是真的很高。

迭代遍历耗时分析

iterator 是每个集合通用功能

迭代遍历耗时分析Java代码

List<Integer> list = new LinkedList<>();
List<Integer> arrayList = new ArrayList<>();

int size = 1;

for (int j = 1; j < 25; j++) {
    size = size * 2;
    // 集合LinkedList初始化
    for (int i = 0; i < size; i++) {
        list.add(i);
    }

    long listBegin = System.nanoTime();
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        iterator.next();
    }
    double listCost = (System.nanoTime() - listBegin) / 1000000.0;
    System.out.print("lists size: " + size + "; get cost time[LinkedList, ArrayList]:[" + listCost);
    list.clear();

    // 集合ArrayList初始化
    for (int i = 0; i < size; i++) {
        arrayList.add(i);
    }
    long arrayListBegin = System.nanoTime();
    Iterator<Integer> arrayListIterator = arrayList.iterator();
    while (arrayListIterator.hasNext()) {
        arrayListIterator.next();
    }
    double arrayCost = (System.nanoTime() - arrayListBegin) / 1000000.0;
    System.out.println("ms, " + arrayCost + "ms]");
    arrayList.clear();
}

性能对决：LinkedList vs ArrayList，结果出乎意料 用二维图展示： 性能对决：LinkedList vs ArrayList，结果出乎意料

小结论

ArrayList 的遍历速度远快于 LinkedList 的遍历，看后面数据，几乎快了100倍，原因有以下2点：

  1. 内存结构：ArrayList 是基于动态数组实现的，而 LinkedList 是基于双向链表实现的。在 ArrayList 中，元素存储在连续的内存空间中，这使得内存访问更加高效。相比之下，LinkedList 中的元素是分散存储的，每个元素都需要一个额外的存储空间来保存指向前一个和后一个元素的引用，这增加了内存访问的开销。
  2. 遍历方式：在遍历 ArrayList 时，由于元素存储的连续性，CPU缓存（如L1、L2缓存）可以更有效地工作，因为相邻的数据更可能被一起加载到缓存中。而 LinkedList 由于元素不连续，导致缓存的局部性原理得不到充分利用，降低了缓存命中率。

性能对比结论

ArrayList 相对于 LinkedList内存容量占用更低，get、add、remove、迭代遍历效率更高， LinkedList 性能方面完败。

使用建议

ArrayList各方面性能完胜LinkedList，如果比较在意性能问题，建议使用ArrayList；那什么情况下可以使用LinkedList ，如果你不在意性能，且经常需要在集合头尾增加或者移除元素，还是使用LinkedList好些，代码可读性更好些，可看以下使用。

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.addLast(value); // 头部添加元素
linkedList.addFirst(value); // 尾部添加元素
linkedList.removeFirst(); // 移除头部元素
linkedList.removeLast();// 移除尾部元素
linkedList.getFirst();// 获取头部元素
linkedList.getLast();// 获取尾部元素

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0, value); // 头部添加元素
arrayList.add(arrayList.size() -1, value); // 尾部添加元素，且需要判断集合是否为空
arrayList.remove(0); // 移除头部元素，且需要判断集合是否为空
arrayList.remove(arrayList.size() -1);// 移除尾部元素，且需要判断集合是否为空
arrayList.get(0); // 获取头部元素，且需要判断集合是否为空
arrayList.get(arrayList.size() -1); // 获取尾部元素，且需要判断集合是否为空