ArrayList 与 LinkedList 性能实测：插入、遍历与删除耗时对比

ArrayList 与 LinkedList 性能实测

以下测试基于本地环境进行，具体耗时可能因硬件配置而异，仅供参考。

1. 尾部追加 (add(E e))

在频繁向集合末尾添加元素时，ArrayList 通常表现更好。LinkedList 每次增加元素都需要新建一个 Entry 对象并进行多次赋值操作，在频繁的系统调用中会对性能产生一定影响。

package list;

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

public class ListPerformanceTest {
    public static void main(String[] args) {
        testAdd();
    }

    static void testAdd() {
        Object obj = new Object();
        List<Object> al = new ArrayList<>(); // 约 70ms
        List<Object> ll = new LinkedList<>(); // 约 471ms
        long b = System.currentTimeMillis();
        for (int i = 0; i < 5000000; i++) {
            al.add(obj); // 添加到尾端
        }
        long e = System.currentTimeMillis();
        System.out.println(e - b);
    }
}

2. 索引插入 (add(int index, E element))

ArrayList 的此方法在源码层面可以看出，每插入一次都会进行一次数组复制。如果数据插入到尾端则不存在此开销，但大量数据重组会导致性能低下。插入位置越靠前，数组重组开销越大。

相比之下，LinkedList 对于插入到前后中的效率基本一致。虽然它需要搜索节点，但在处理头部插入时优势明显。

    static void testAddIndex() {
        Object obj = new Object();
        List<Object> al = new ArrayList<>(); // 约 1071ms
        List<Object> ll = new LinkedList<>(); // 约 17ms
        long b = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            ll.add(0, obj); // 添加到头部
        }
        long e = System.currentTimeMillis();
        System.out.println(e - b);
    }

3. 随机访问与遍历 (get(i))

遍历列表主要有三种方式，当数据量达到 100 万级别时差异显著：

• for (Object o : list)
• for (Iterator it = list.iterator(); it.hasNext(); )
• for (int i = 0; i < list.size(); i++)

ArrayList 支持随机访问，时间复杂度为 O(1)。而 LinkedList 不支持随机访问，通过下标获取元素需从头或尾遍历，数据量大时耗时极长。

    static void testQuery() {
        List<String> l = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            l.add(String.valueOf(i));
        }
        long b = System.currentTimeMillis();
        String temp = "";
        for (int i = 0; i < l.size(); i++) {
            temp = l.get(i);
        }
        long e = System.currentTimeMillis();
        System.out.println(e - b);
    }

测试结果参考：

• ArrayList: 1w 条 2ms，10w 条 5ms，100w 条 10ms
• LinkedList: 1w 条 94ms，10w 条 13174ms，100w 条 超时

由此可知，在遍历和随机读取数据方面，ArrayList 具有明显的优势。实际开发中应根据具体的业务场景选择合适的数据结构。