🌺The Begin🌺点点关注，收藏不迷路🌺

在 Java 开发中，数组 和 链表 是两种最基础、也最重要的线性数据结构。虽然它们都能按顺序存储数据，但底层内存模型截然不同，导致其增删改查的性能表现、使用场景也天差地别。

本文将深入剖析二者的本质区别，并通过流程图、代码示例和性能对比，帮你彻底理解“什么时候用数组，什么时候用链表”。

1. 底层存储结构对比

1.1 数组：连续内存块

数组在内存中是一段 连续的内存空间。创建数组时，Java 会一次性申请一个固定大小的连续区域。

int[] arr = new int[5]; // 连续申请 5 个 int 大小的空间

流程图：数组内存布局

1.2 链表：零散节点 + 指针

链表由一系列 不连续 的节点组成，每个节点包含 数据域 和 指针域（指向下一个节点的地址）。

class ListNode {
    int val;
    ListNode next; // 指向下一个节点
}

流程图：单链表内存布局

2. 核心操作性能差异（重点）

操作	数组	链表（单向）	说明
按下标访问	O(1) ✅	O(n) ❌	数组直接计算地址，链表需遍历
头部插入	O(n) ❌	O(1) ✅	数组需移动所有元素
尾部插入	O(1)（有扩容时 O(n)）	O(1)（有 tail 指针）	数组可能触发扩容复制
中间插入	O(n)	O(n)（查找定位 + O(1) 改指针）	查找成为瓶颈
删除	O(n)（移动元素）	O(1)（已知前驱节点时）	数组元素整体迁移
内存占用	仅数据	数据 + 指针（8 字节/节点）	链表有额外开销

2.1 数组按下标访问为什么快？

int[] arr = {10, 20, 30};
// 访问 arr[2] 时，JVM 计算：起始地址 + 2 * 4 字节 = 直接取值

2.2 链表插入为什么快（头部）？

只需要修改两处指针，无需移动任何已有元素。

3. 扩容机制对比

3.1 数组：固定长度 + 动态扩容

数组一旦创建，长度不可变。当需要更多空间时，必须：

1. 创建新数组（一般为原长度 1.5 倍）
2. 复制旧数组元素
3. 丢弃旧数组

int[] old = new int[5];
int[] newArr = Arrays.copyOf(old, old.length * 2); // 耗时 O(n)

3.2 链表：无扩容概念

链表动态增加节点，只需在堆上分配一个新节点并调整指针，没有一次性复制所有元素的开销。

4. 类型安全与泛型支持

4.1 数组：协变 + 运行时类型检查

String[] strings = new String[10];
Object[] objects = strings;        // 允许协变
objects[0] = 1;                    // 运行时抛出 ArrayStoreException

数组在运行时才知道具体类型。

4.2 链表：不变 + 编译时类型检查（泛型）

List<String> list = new LinkedList<>();
// list.add(1); // 编译报错，类型安全

通过泛型在编译期杜绝类型错误。

5. 内存碎片与局部性原理

5.1 数组缓存友好

由于连续存储，数组能充分利用 CPU 缓存行。遍历数组时，相邻元素会一起加载到缓存，速度极快。

5.2 链表缓存不友好

链表节点散落在堆内存各处，遍历时频繁缺页中断，导致缓存命中率低。在千万级数据遍历中，数组比链表快 2~5 倍。

6. Java 中的典型实现类对比

特性	ArrayList	LinkedList
底层结构	数组	双向链表
随机访问	O(1)	O(n)
插入/删除（头部/中部）	O(n)	O(1)（已找到位置）
内存占用	较小	较大（额外 prev/next 指针）
实现接口	List, RandomAccess	List, Deque

// 正确使用场景
List<Integer> list = new ArrayList<>(); // 频繁查找、遍历
Queue<Integer> queue = new LinkedList<>(); // 频繁头尾操作

7. 实战选型决策流程图

8. 总结对比表

维度	数组	链表
内存连续性	连续	非连续
长度可变性	不可变（需复制扩容）	动态
随机访问效率	极高	极低
插入删除效率（头/中）	低	高（已知前驱）
额外内存开销	无	每个节点一个引用
缓存友好性	优秀	较差
适用场景	读多写少、下标访问	写多读少、队列/栈实现

9. 一句话记忆口诀

数组查改快，链表增删快；随机访问数组强，频繁操作链表来。

在实际开发中，绝大多数场景 ArrayList 因为缓存优势和足够的增删性能（尾部操作多）而胜出。只有当你明确需要频繁在头部/中间插入删除时，才考虑 LinkedList。

---

如果觉得这篇文章对你有帮助，欢迎点赞、收藏、转发，让更多 Java 开发者看清数组与链表的本质。

🌺The End🌺点点关注，收藏不迷路🌺