数组是一种基本的线性数据结构，它由一组**连续内存空间中存储的相同类型元素**组成

数组是一种基本的线性数据结构它由一组连续内存空间中存储的相同类型元素组成通过**下标索引**进行随机访问时间复杂度 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到A31字节一次性载入L1/L2缓存后续对同一行内其他地址的访问可直接命中缓存极快避免昂贵的主存访问。数组的缓存友好性时间/空间局部性假设有一个int arr[1000]每个int占4字节元素在内存中连续存放地址: 0x1000 0x1004 0x1008 0x100C ... 0x1FFC 值: arr[0] arr[1] arr[2] arr[3] ... arr[999]当遍历for (int i0; i1000; 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 ...遍历链表时访问head0x2A00→ 加载含head.val和head.next的缓存行0x2A00–0x2A3F但head.next指向0x3F80远超64B范围→必然缓存未命中需另一次主存访问每次取next指针都大概率触发新缓存行加载大量随机访存命中率常低于20%性能受内存延迟主导纳秒级 vs 缓存命中仅0.5ns。✅ 关键结论数组利用空间局部性使一次主存访问服务多次计算链表因节点离散破坏局部性导致“缓存抖动”Cache Thrashing即使理论复杂度相同如O(n)遍历实际运行时间可能是数组的3–10倍实测常见。