Java 中如何选择：ArrayList 还是 LinkedList？-编程学习网

ArrayList

ArrayList 是一个动态数组，基于数组实现。它的主要优点是访问速度快，但在插入和删除元素时性能较低，特别是在数组中间或开始位置进行操作时。

优点

快速随机访问：ArrayList 支持 O(1) 时间复杂度的随机访问，因为它内部是数组实现的。
节省空间：相对于 LinkedList，ArrayList 消耗的内存更少，因为它不需要为每个元素存储额外的指针。

缺点

插入和删除操作慢：在 ArrayList 中插入或删除元素（尤其是在中间位置）会导致数组重新分配和元素移动，时间复杂度为 O(n)。
固定容量限制：虽然 ArrayList 会动态扩展，但当它需要扩展时，会消耗额外的性能来进行数组复制。

适用场景

列表大小相对固定或变化不大。
需要频繁访问元素的场景。

示例代码

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList<>();

        // 添加元素
        arrayList.add("Java");
        arrayList.add("Python");
        arrayList.add("C++");

        // 访问元素
        System.out.println("Element at index 1: " + arrayList.get(1));

        // 插入元素
        arrayList.add(1, "JavaScript");
        System.out.println("After insertion: " + arrayList);

        // 删除元素
        arrayList.remove("Python");
        System.out.println("After deletion: " + arrayList);
    }
}

LinkedList

LinkedList 是一个双向链表，每个元素都是一个节点，每个节点包含数据和指向前一个及后一个节点的指针。它的主要优点是插入和删除操作快，但随机访问速度慢。

优点

快速插入和删除：LinkedList 在任意位置插入和删除元素的时间复杂度为 O(1)，只需要调整相关节点的指针。
没有容量限制：LinkedList 没有固定的大小限制，可以随时添加和删除元素。

缺点

随机访问慢：访问 LinkedList 中的元素需要从头节点开始遍历，时间复杂度为 O(n)。
内存消耗大：由于每个节点都需要存储额外的指针，LinkedList 比 ArrayList 消耗更多的内存。

适用场景

列表大小动态变化，需要频繁插入和删除元素的场景。
不需要频繁访问元素的场景。

示例代码

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList<>();

        // 添加元素
        linkedList.add("Java");
        linkedList.add("Python");
        linkedList.add("C++");

        // 访问元素
        System.out.println("Element at index 1: " + linkedList.get(1));

        // 插入元素
        linkedList.add(1, "JavaScript");
        System.out.println("After insertion: " + linkedList);

        // 删除元素
        linkedList.remove("Python");
        System.out.println("After deletion: " + linkedList);
    }
}

如何选择

在选择 ArrayList 和 LinkedList 时，你需要考虑以下几个因素：

访问频率：如果应用程序需要频繁访问列表中的元素，ArrayList 是更好的选择。
修改频率：如果应用程序需要频繁插入和删除元素，尤其是在列表的中间位置，LinkedList 是更好的选择。
内存使用：如果内存使用是一个关键因素，且列表大小较大，ArrayList 相对更节省内存。
线程安全：ArrayList 和 LinkedList 都不是线程安全的。如果需要在多线程环境中使用，可以考虑使用 Collections.synchronizedList 包装它们，或者使用 CopyOnWriteArrayList 和 ConcurrentLinkedDeque 等线程安全的变体。