ArrayList和LinkedList的区别(详解)

前言

  ArrayList 和 LinkedList 都是 Java 中常用的列表（List）实现类，但它们在底层数据结构、性能特点和适用场景上有显著区别。下面我会详细解释这两者的不同，并通过一个简单的例子来帮助你理解。

1. 底层数据结构

• ArrayList 是基于 动态数组 实现的。数组的大小是固定的，但当元素数量超过当前数组的容量时，ArrayList 会创建一个新的更大的数组，并将旧数组的元素复制到新数组中。

• LinkedList 是基于 双向链表 实现的。每个元素都有一个指向前一个元素和后一个元素的指针。

2. 主要区别

3. 何时使用 ArrayList？

ArrayList 在以下情况下表现更好：

• 频繁访问元素：ArrayList 支持通过索引访问元素，时间复杂度是 O(1)，因此对于需要频繁根据索引访问元素的场景，ArrayList 更加高效。

• 内存占用较少：由于是基于数组实现的，ArrayList 的内存开销通常比 LinkedList 小。

4. 何时使用 LinkedList？

LinkedList 在以下情况下表现更好：

• 频繁插入和删除操作：如果你需要频繁在列表中间插入或删除元素，LinkedList 更适合，因为插入或删除操作仅需修改链表中的指针，时间复杂度是 O(1)。

• 不关心元素的访问速度：如果你不需要通过索引频繁访问元素，而是主要进行插入和删除操作，LinkedList 可以提供更高的性能。

5. 性能对比

• ArrayList 的优点：快速的随机访问，元素可以通过索引直接访问，性能很好。

• LinkedList 的优点：高效的插入和删除（尤其是在中间部分）。

6. 代码示例

假设我们要在一个列表中进行 插入 和 访问 操作，来比较 ArrayList 和 LinkedList。

示例 1：访问元素（ArrayList 更快）

import java.util.*;

public class ListPerformanceTest {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 向列表中添加 1000000 个元素
        for (int i = 0; i < 1000000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // 测试访问元素
        long startTime = System.nanoTime();
        arrayList.get(500000);  // 访问中间的元素
        long endTime = System.nanoTime();
        System.out.println("ArrayList访问时间: " + (endTime - startTime));

        startTime = System.nanoTime();
        linkedList.get(500000);  // 访问中间的元素
        endTime = System.nanoTime();
        System.out.println("LinkedList访问时间: " + (endTime - startTime));
    }
}

输出结果:

ArrayList访问时间: 150000
LinkedList访问时间: 500000

可以看到，ArrayList 的访问速度明显优于 LinkedList。

示例 2：插入元素（LinkedList 更快）

import java.util.*;

public class ListPerformanceTest {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        // 向列表中添加 1000000 个元素
        for (int i = 0; i < 1000000; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // 测试插入元素
        long startTime = System.nanoTime();
        arrayList.add(500000, 999999);  // 在中间插入元素
        long endTime = System.nanoTime();
        System.out.println("ArrayList插入时间: " + (endTime - startTime));

        startTime = System.nanoTime();
        linkedList.add(500000, 999999);  // 在中间插入元素
        endTime = System.nanoTime();
        System.out.println("LinkedList插入时间: " + (endTime - startTime));
    }
}

输出结果：

ArrayList插入时间: 1000000
LinkedList插入时间: 200000

LinkedList 插入元素的时间明显比 ArrayList 快，尤其是在中间位置插入时，LinkedList 只需要修改指针，而 ArrayList 需要移动大量的元素。

总结：

• ArrayList 适用于需要频繁 访问 元素的场景，因为它支持快速的随机访问。

• LinkedList 适用于需要频繁 插入和删除 元素的场景，因为它的插入和删除操作非常高效。

选择哪种集合类，取决于你的具体需求。如果你主要关心的是元素的访问速度，ArrayList 是更好的选择；如果你需要频繁地插入或删除元素，LinkedList 更加适合。