ArrayList VS LinkedList：从底层原理到性能对决

2401_89765726

1036人浏览 · 2026-03-01 19:46:40

2401_89765726 · 2026-03-01 19:46:40 发布

一、开篇：为什么数组总是从0开始？

在学习集合之前，我们先来思考一个基础问题：为什么数组的索引总是从0开始，而不是从1开始？

这其实是历史遗留和性能考虑的结果。在计算机底层，数组是一块连续的内存空间，当我们访问数组的第i个元素时，计算机会通过一个公式来定位它的内存地址：

第i个元素的地址 = 数组首地址 + i × 每个元素占用的字节数

如果索引从0开始，计算起来就是上面的公式，非常简单。但如果索引从1开始，公式就变成了：

第i个元素的地址 = 数组首地址 + (i-1) × 每个元素占用的字节数

每次访问都要多一次减法运算。虽然看起来微不足道，但在计算机底层，这种微小的性能差异积累起来就是可观的提升。所以C语言设计者选择了从0开始，后来的Java也沿用了这个设计。

二、数组的特点与局限

数组是Java中最基础的数据结构，它有两大特点：

优点：内存空间连续，通过索引访问元素的时间复杂度是O(1)，极快！

缺点：一旦创建，长度就固定了，不能动态增加。比如你创建了一个长度为10的数组，存了8个元素后想存第9个没问题，但想存第11个就装不下了。

int[] arr = new int[10];  // 长度固定为10
arr[0] = 1;
arr[1] = 2;
// ... 存到 arr[9] 是极限了
arr[10] = 11;  // 数组下标越界！

正是为了解决数组不能动态增长的痛点，Java推出了ArrayList。

三、ArrayList：升级版的数组

3.1 底层结构

ArrayList的底层就是一个数组，但它比普通数组聪明的地方在于：它会自动扩容。

// 创建ArrayList
ArrayList<String> list = new ArrayList<>();
list.add("张三");  
list.add("李四");

当你创建ArrayList时，它内部会初始化一个数组（默认容量是10）。当你往里面添加元素，发现数组装满了，ArrayList会怎么做呢？

3.2 扩容机制

ArrayList的扩容规则是：当数组满了需要添加新元素时，会创建一个新的数组，新数组的大小是原数组的1.5倍，然后把原数组的所有元素复制过去，最后释放原数组的内存。

// 伪代码展示ArrayList扩容逻辑
if (当前元素个数 == 数组长度) {
    int 新容量 = 原容量 + (原容量 >> 1);  // 右移一位相当于除以2，所以是1.5倍
    Object[] 新数组 = new Object[新容量];
    System.arraycopy(原数组, 0, 新数组, 0, 原容量);
    原数组 = 新数组;  // 指向新数组
}

3.3 访问元素为什么快？

因为ArrayList的底层是数组，内存空间连续，所以通过索引访问元素直接就是O(1)的时间复杂度：

String name = list.get(5);  // 直接定位到第5个元素的位置，瞬间拿到

四、LinkedList：基于节点的链表

4.1 底层结构

LinkedList的底层是双向链表，它由一个个节点（Node）组成，每个节点包含三部分：数据、指向前一个节点的引用、指向后一个节点的引用。

// 伪代码展示LinkedList内部节点结构
class Node {
    Object item;      // 存储的数据
    Node prev;        // 指向前一个节点
    Node next;        // 指向后一个节点
}

4.2 链表的特点

优点：添加和删除元素理论上很快，只需要修改前后节点的指向，不需要移动其他元素。

缺点：不能通过索引直接访问元素。比如你想获取第5个元素，LinkedList只能从头节点开始，一个一个往后找，直到找到第5个。

LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.add("C");
// ... 添加很多元素

String element = linkedList.get(100);  
// 需要从第0个开始，next->next->next... 找100次！

五、缓存对性能的影响

5.1 什么是CPU缓存？

CPU处理数据的速度极快，而内存读取数据的速度相对较慢。为了解决这个速度不匹配的问题，CPU内部嵌入了一块小而快的内存，叫做缓存（Cache）。

缓存的工作原理是：当CPU读取一个内存地址的数据时，它会把这个地址附近的一块数据也一起加载到缓存中。因为程序访问内存时往往具有局部性原理——访问了一个地址，很可能很快就会访问它附近的地址。

5.2 连续存储 vs 离散存储

ArrayList的优势：数组在内存中是连续存储的，遍历时CPU会把整个数组块加载到缓存，后面的访问都直接从缓存中读取，速度极快。

// 遍历ArrayList - 缓存友好
for (int i = 0; i < arrayList.size(); i++) {
    System.out.println(arrayList.get(i));  
    // CPU预加载了连续的内存，大部分访问命中缓存
}

LinkedList的劣势：链表的节点在内存中是离散的，可能分散在各个角落。遍历时，访问完一个节点，下一个节点可能在很远的地方，CPU需要不断从内存重新加载数据到缓存，缓存命中率低。

// 遍历LinkedList - 缓存不友好
for (String s : linkedList) {
    System.out.println(s);
    // 每个节点都可能在不同位置，CPU缓存几乎用不上
}

这就是为什么实际测试中，遍历LinkedList往往比ArrayList慢很多的原因之一。

六、删除操作

教科书上常说：LinkedList的增删操作快，ArrayList的增删操作慢。但这个结论需要仔细推敲。

6.1 理论上的对比

ArrayList删除元素：

// 删除索引为5的元素
arrayList.remove(5);
// 需要把索引6、7、8...的所有元素向前移动一位
// 时间复杂度 O(n)

LinkedList删除元素：

// 删除索引为5的元素
linkedList.remove(5);
// 只需要修改节点5前后两个节点的指向
// 但是！必须先找到节点5
// 找节点的过程是 O(n)，修改指向是 O(1)
// 总复杂度还是 O(n)

6.2 现实中的真相

删除操作的核心成本有两部分：

查找目标元素的时间
真正删除的时间

对于ArrayList：

查找：O(1)（直接索引）
删除后移动元素：O(n)
总成本：O(n)

对于LinkedList：

查找：O(n)（需要遍历到目标位置）
删除（修改指针）：O(1)
总成本：O(n)

关键点来了：虽然两者都是O(n)，但ArrayList的O(n)是内存连续的移动操作，CPU缓存友好；LinkedList的O(n)是遍历节点，每个节点都可能缓存缺失。所以实际情况往往是：ArrayList的删除比LinkedList更快！

测试一下：

// 测试删除中间元素
ArrayList<Integer> arrayList = new ArrayList<>();
LinkedList<Integer> linkedList = new LinkedList<>();

// 都添加100万条数据
for (int i = 0; i < 1000000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// 删除中间位置的元素
long start1 = System.currentTimeMillis();
arrayList.remove(500000);
long end1 = System.currentTimeMillis();
System.out.println("ArrayList删除耗时：" + (end1 - start1) + "ms");

long start2 = System.currentTimeMillis();
linkedList.remove(500000);
long end2 = System.currentTimeMillis();
System.out.println("LinkedList删除耗时：" + (end2 - start2) + "ms");

// 结果：
// ArrayList删除耗时：8ms
// LinkedList删除耗时：15ms

6.3 什么时候LinkedList真的快？

只有当你在链表头部或者已知节点位置进行增删时，LinkedList才真正体现优势：

// LinkedList的优势场景
linkedList.addFirst("开头插入");  // O(1)，不需要查找
linkedList.removeFirst();        // O(1)，删除头节点

// 或者你已经通过遍历拿到了某个节点
ListIterator<String> it = linkedList.listIterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("某个条件")) {
        it.remove();  // 基于当前节点删除，O(1)
        break;
    }
}