数组是一种基本的线性数据结构，它由一组**连续内存空间中存储的相同类型元素**组成
数组是一种基本的线性数据结构，它由一组连续内存空间中存储的相同类型元素组成，通过**下标（索引）**进行随机访问（时间复杂度 O(1)）。数组具有固定大小（静态数组）或动态扩容能力（如动态数组/ArrayList），支持快速读取，但插入和删除（尤其在中间位置）通常需移动元素，平均时间复杂度为 O(n)。常见变体包括一维数组、多维数组（如二维数组用于矩阵）、以及基于数组实现的其他结构（如栈、队列、哈希表底层等）。
数组与链表的核心区别体现在内存布局和由此决定的时间复杂度特性上：
🔹内存布局：
- 数组：元素在内存中连续存储（一块固定或动态分配的连续空间），通过首地址 + 偏移量（
base_addr + index × element_size）直接计算地址。 - 链表：元素（节点）分散存储在堆内存中，每个节点包含数据域和指向下一节点的指针（单向/双向），逻辑顺序靠指针链接，物理地址不连续。
🔹时间复杂度对比：
| 操作 | 数组（静态/动态） | 链表（单向，带头结点） | 原因说明 |
|---|---|---|---|
| 随机访问 | O(1) ✅ | O(n) ❌ | 数组支持地址直接计算；链表需从头逐个遍历。 |
| 头部插入/删除 | O(n) ❌（需移动元素） | O(1) ✅ | 链表只需修改头指针和新节点指针；数组所有元素需平移。 |
| 尾部插入（动态数组） | 均摊 O(1) ✅（扩容时O(n)） | O(1) ✅（需维护尾指针） | 动态数组扩容触发复制，但分摊后仍为常数；链表尾插若无尾指针则为O(n)。 |
| 中间插入/删除 | O(n) ❌（平均移动n/2元素） | O(n) ❌（先查找再修改指针） | 数组移动开销大；链表查找耗时，但指针修改本身O(1)。 |
✅ 补充关键点：
- 数组缓存友好（局部性原理强，预取高效）；链表节点分散，易造成缓存未命中。
- 链表更灵活（动态大小、无需预估容量），但每节点有额外指针开销（如64位系统中指针占8字节）；数组空间利用率高，但可能浪费（如预分配过大）或受限（静态数组无法扩容）。
“数组的缓存局部性优于链表”源于其物理内存连续性与CPU缓存行（Cache Line）预取机制的高度契合。以下是具体解释与示例：
🔹缓存行（Cache Line）机制简述：
现代CPU从主存读取数据时，并非只加载单个变量，而是以固定大小块（通常64字节）为单位——即一个缓存行。当访问地址A时，CPU会将包含A的整个缓存行（如A−32到A+31字节）一次性载入L1/L2缓存，后续对同一行内其他地址的访问可直接命中缓存（极快），避免昂贵的主存访问。
🔹数组的缓存友好性（时间/空间局部性）：
假设有一个int arr[1000]（每个int占4字节），元素在内存中连续存放：
地址: 0x1000 0x1004 0x1008 0x100C ... 0x1FFC 值: arr[0] arr[1] arr[2] arr[3] ... arr[999]当遍历for (int i=0; i<1000; i++) sum += arr[i];：
- 访问
arr[0]（地址0x1000）→ 触发加载缓存行0x1000–0x103F→ 同时载入arr[0]到arr[15]（64B ÷ 4B = 16个int）； - 接着访问
arr[1]~arr[15]全部命中缓存，零主存延迟； - 下一轮访问
arr[16]又触发新缓存行加载，但整体命中率极高（>90%），吞吐量接近内存带宽极限。
🔹链表的缓存不友好性（空间局部性差）：
链表节点通常动态分配（malloc/new），内存位置随机：
structNode{intval;Node*next;};// 8字节（int4 + ptr4）// 节点可能分散在：0x2A00 → 0x3F80 → 0x1C40 → 0x7E20 ...遍历链表时：
- 访问
head（0x2A00）→ 加载含head.val和head.next的缓存行（0x2A00–0x2A3F）； - 但
head.next指向0x3F80（远超64B范围）→必然缓存未命中，需另一次主存访问； - 每次取
next指针都大概率触发新缓存行加载，大量随机访存，命中率常低于20%，性能受内存延迟主导（纳秒级 vs 缓存命中仅0.5ns）。
✅ 关键结论：
数组利用空间局部性，使一次主存访问服务多次计算；链表因节点离散，破坏局部性，导致“缓存抖动”（Cache Thrashing），即使理论复杂度相同（如O(n)遍历），实际运行时间可能是数组的3–10倍（实测常见）。