Java 集合中ArrayList与LinkedList的性能比较

一、需求：

1. 头部插入‌：向列表头部插入10万个整数。
2. ‌随机访问‌：从列表中间位置连续获取1万个元素。
3. ‌头部删除‌：从列表头部连续删除10万个元素。

二、 使用ArrayList与LinkedList测试

 //常量定义，用于测试操作的次数
    private static final int INSERT_COUNT = 100000;
    private static final int ACCESS_COUNT = 10000;
    private static final int DELETE_COUNT = 100000;

    public static void main(String[] args) {
        // 测试ArrayList
        List<Integer> arrayList = new ArrayList<>();
        System.out.println("ArrayList头部插入耗时: " + insertAtHead(arrayList, INSERT_COUNT) + "ms");
        System.out.println("ArrayList随机访问耗时: " + accessMiddle(arrayList, ACCESS_COUNT) + "ms");
        System.out.println("ArrayList头部删除耗时: " + deleteFromHead(arrayList, DELETE_COUNT) + "ms");
        System.out.println("***************************************************************");

        // 测试LinkedList
        List<Integer> linkedList = new LinkedList<>();
        System.out.println("LinkedList头部插入耗时: " + insertAtHead(linkedList, INSERT_COUNT) + "ms");
        System.out.println("LinkedList随机访问耗时: " + accessMiddle(linkedList, ACCESS_COUNT) + "ms");
        System.out.println("LinkedList头部删除耗时: " + deleteFromHead(linkedList, DELETE_COUNT) + "ms");
    }

    // 头部插入计时方法
    private static long insertAtHead(List<Integer> list, int count) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            list.add(0, i); // 头部插入
        }
        return System.currentTimeMillis() - start;
    }

    // 中间位置随机访问计时方法
    private static long accessMiddle(List<Integer> list, int count) {
        if (list.isEmpty()) return 0;
        long start = System.currentTimeMillis();
        int middle = list.size() / 2;
        for (int i = 0; i < count; i++) {
            list.get(middle); // 访问中间元素
        }
        return System.currentTimeMillis() - start;
    }

    // 头部删除计时方法
    private static long deleteFromHead(List<Integer> list, int count) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < count; i++) {
            if (!list.isEmpty()) {
                list.remove(0); // 头部删除
            }
        }
        return System.currentTimeMillis() - start;
    }

三、效果

四、总结分析：

1. ‌头部插入‌

   • ‌结果‌：LinkedList耗时远小于ArrayList。
   • ‌原因‌：ArrayList需要将后续元素向后移动（时间复杂度O(n)），而LinkedList只需修改指针（时间复杂度O(1)）。

2. ‌随机访问‌

   • ‌结果‌：ArrayList耗时远小于LinkedList。
   • ‌原因‌：ArrayList基于数组实现，可直接通过索引定位（时间复杂度O(1)），而LinkedList需要从头遍历（时间复杂度O(n)）。

3. ‌头部删除‌

   • ‌结果‌：LinkedList耗时小于ArrayList。
   • ‌原因‌：LinkedList只需调整头节点指针（O(1)），而ArrayList需要移动剩余元素（O(n)）。

    由上述测试：   ArrayList实现了长度可变的数组，在内存中分配连续的空间，遍历元素和随机访问元素的效率比较高 ；LinkedList采用链表存储方式，插入、删除元素时效率比较高。