在 Java 开发中，List 接口是我们最常打交道的数据结构之一。而实现该接口的两个最主要类——ArrayList 和 LinkedList，它们各有千秋。了解它们的底层原理，是写出高性能代码的关键。

本文将带你深入理解它们的内部机制、性能差异，以及如何解决 ArrayList 的线程安全问题。

1. ArrayList：动态数组的王者

底层原理与内存结构

ArrayList 的本质是一个动态数组。

• 连续内存：它在内存中开辟了一块连续的存储空间来存放数据。
• 随机访问：得益于连续内存的特性，ArrayList 可以通过索引（数组下标）直接计算出元素的内存地址。这意味着它的随机查找速度非常快，时间复杂度为 $O(1)$。

关键机制：自动扩容

数组在创建时长度是固定的，那么 ArrayList 是如何做到“动态”的呢？答案是自动扩容机制。

1. 初始容量：当我们创建一个空的 ArrayList 时，它默认的初始容量是 10。
2. 触发扩容：当向容器中添加元素时，如果当前元素个数已经达到了数组的容量上限，就会触发扩容。
3. 扩容过程：
   • 创建一个新的数组，其大小约为原数组的 1.5 倍（具体算法是 oldCapacity + (oldCapacity >> 1)）。
   • 将原数组中的所有数据通过 System.arraycopy 复制到新数组中。
   • 丢弃旧数组，使用新数组。

注意：扩容是一个比较消耗性能的操作，因为它涉及内存分配和数据的大量复制。因此，如果在创建 ArrayList 时就能预估数据大概的大小，建议指定初始容量：new ArrayList<>(预估大小)，以减少扩容次数。

优缺点分析

• 优点（查）：查找快。如前所述，基于索引的随机访问效率极高。
• 缺点（增删）：增删慢。
  • 扩容开销：添加元素导致扩容时，性能损耗大。
  • 元素位移：如果在数组中间插入或删除元素，为了保持内存连续性，该位置之后的所有元素都需要向前或向后移动，时间复杂度为 $O(n)$。

---

2. LinkedList：灵活的链表

底层原理与内存结构

LinkedList 的底层是一个双向链表（JDK 1.7 以后）。

• 离散内存：它的数据元素在内存中不是连续存放的，而是散落在各个角落。
• 节点链接：每个数据元素被封装在一个“节点 (Node)”对象中。每个节点除了保存数据本身，还保存了指向前一个节点的引用（prev）和指向后一个节点的引用（next）。

Java

// LinkedList 内部 Node 类的简化示意
private static class Node<E> {
    E item;        // 数据
    Node<E> next;  // 指向下一个节点的指针
    Node<E> prev;  // 指向前一个节点的指针
    // ...
}

优缺点分析

• 优点（增删）：增删快。
  • LinkedList 没有扩容机制，理论上只要内存足够，可以无限添加。
  • 在链表的任意位置插入或删除元素，只需要改变目标位置前后两个节点的指针指向即可，不需要移动其他任何元素，时间复杂度为 $O(1)$（前提是已经找到了要操作的位置）。
• 缺点（查）：查找慢。
  • 由于内存不连续，无法通过索引计算地址。要查找第 N 个元素，必须从链表头（或尾）开始一个一个向后遍历，直到找到目标元素，时间复杂度为 $O(n)$。

---

3. 核心对比总结

理解了上面的原理，我们将它们的区别整理如下表，这是面试中的高频考点：

特性	ArrayList (动态数组)	LinkedList (双向链表)	核心原因
底层结构	Object[] 数组	双向链表节点 Node	根本区别
内存分布	连续的内存空间	离散的内存空间	影响访问方式
随机访问 (Get)	快，$O(1)$	慢，$O(n)$，需要遍历	数组可通过下标计算地址；链表只能顺藤摸瓜
中间增删	慢，$O(n)$，涉及元素位移	快，$O(1)$，只需修改指针	数组要保持连续性；链表只需改链接
扩容机制	有，默认 10，1.5倍扩容，伴随数据复制	无，动态申请节点	数组定长特性决定
空间占用	尾部可能存在未使用的空间	每个元素需要额外空间存储指针	不同的空间浪费方式
适用场景	读多写少，需要快速随机访问	写多读少，频繁在头部或中间增删数据	扬长避短

---

4. 进阶：如何保证 ArrayList 的线程安全

标准的 java.util.ArrayList 是线程不安全的。在多线程环境下并发读写，可能会导致抛出 ConcurrentModificationException 异常，或者数据丢失、数据覆盖等严重问题。

如果需要在多线程环境中使用类似数组的结构，有以下三种主要方案：

方案一：Collections.synchronizedList()

这是最简单的办法，利用 JDK 提供的工具类，将一个普通的 ArrayList 包装成线程安全的 List。

• 原理：它返回一个代理类，这个代理类在调用底层 ArrayList 的所有方法（add, get, remove 等）时，都加上了一个粗粒度的对象锁（synchronized mutex）。
• 缺点：并发度低，所有操作都在竞争同一把锁，性能一般。

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SyncListDemo {
    public static void main(String[] args) {
        // 创建一个普通的 ArrayList
        ArrayList<String> unsafeList = new ArrayList<>();
        
        // 将其包装为线程安全的 List
        List<String> safeList = Collections.synchronizedList(unsafeList);

        // 在多线程环境中使用 safeList
        // 注意：虽然单个方法原子化了，但复合操作（如遍历时修改）仍需手动加锁
        synchronized(safeList) {
             for (String s : safeList) {
                 // 迭代操作
             }
        }
    }
}

方案二：Vector (古老的替代者)

Vector 是 JDK 1.0 就存在的古老集合类。

• 原理：它的底层结构与 ArrayList 几乎完全一样（也是动态数组），但它在类的定义中，将几乎所有 public 方法都加上了 synchronized 关键字修饰。
• 缺点：锁的粒度太大，无论读写都加锁，导致性能非常低下。在现代 Java 开发中，基本已经废弃，不推荐使用。

方案三：CopyOnWriteArrayList (JUC 神器)

这是 java.util.concurrent (JUC) 包下提供的高并发解决方案，是处理“读多写少”并发场景的最佳选择。

• 原理（读写分离，最终一致性）：
  • 读操作（Get）：不加任何锁，直接读取当前的数组。性能极高。
  • 写操作（Add/Set/Remove）：为了保证写入时不影响读取，它不会直接修改原数组。而是先加锁，然后将原数组复制一份生成一个新的副本数组。在副本数组上进行修改操作。修改完成后，再将内部的引用指向这个新的副本数组。
• 适用场景：非常适合读操作远远多于写操作的场景（如白名单、黑名单、配置列表等）。
• 缺点：
  • 内存占用高：每次写操作都要复制数组，如果数据量大，内存压力极大。
  • 数据一致性：只能保证数据的最终一致性，不能保证实时一致性（因为写的时候，读线程读到的还是旧数据）。

Java

import java.util.concurrent.CopyOnWriteArrayList;

public class CowListDemo {
    public static void main(String[] args) {
        // 直接创建 CopyOnWriteArrayList
        CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();

        // 多线程可以安全地并发读写
        Thread t1 = new Thread(() -> {
            cowList.add("Data 1"); // 写操作会触发复制
            cowList.add("Data 2");
        });

        Thread t2 = new Thread(() -> {
            // 读操作无需加锁，可能读到旧数据，但不会报错
            for (String s : cowList) {
                System.out.println("读取: " + s);
            }
        });
        
        t1.start();
        t2.start();
    }
}