写在前面
在写完动态顺序表的增删改查、单链表的反转与相交等经典题型后，我曾一度以为自己已经吃透了这两种最基础的线性表。在最初的认知里，二者的区别无非就是：顺序表是连续的数组，按下标找元素快；链表是节点加指针，插删方便。
但越往深学越发现，数据结构的性能差异，从来不止停留在代码层面。很多面试里高频追问的问题：
为什么同样是 O(N) 遍历，数组实际运行速度远快于链表？
为什么 C++ 标准库里 vector 的使用频率远高于 list？
为什么很多高频场景明明需要插删，大家还是优先用数组？
答案都不在数据结构本身，而在计算机底层的内存组织与硬件特性里。
本文跳出纯接口实现的层面，从存储结构本质、内存管理逻辑、CPU 缓存机制三个维度，把顺序表与链表的底层差异讲透。搞懂这些再去学栈、队列、二叉树，就不只是在背 API，而是能真正理解「为什么要这么设计」。
一、核心差异的根源：存储结构的本质不同
所有操作复杂度的区别，本质都来自「内存是否连续」这一个核心特征。
1. 顺序表：连续内存天然支持随机访问
顺序表的本质，是一整块物理地址连续的内存空间，元素紧密排列、没有间隙。
假设首元素地址为 1000，每个 int 占 4 字节，内存布局就是：
复制代码
地址： 1000 1004 1008 1012
数据： [10] [20] [30] [40]
想要访问第 i 个元素，只需要一次简单的地址计算：
复制代码
元素地址 = 首地址 + i × 单个元素大小
无论访问第 1 个还是第 10000 个元素，计算步数完全固定，和数据总量无关。这就是随机访问 O(1) 的底层原理，也是顺序表最核心的优势。
2. 链表：离散节点靠指针串联
链表的每个节点由「数据域 + 指针域」组成，节点之间通过指针相连，但节点在物理内存中没有连续的要求。
逻辑上它是一条链：
复制代码
[10|next] → [20|next] → [30|NULL]
但实际物理地址可能完全分散：
复制代码
地址： 1000 5000 3020
数据： [10|*] ---> [20|*] ---> [30|NULL]
CPU 无法通过公式直接算出第 i 个节点的位置，只能从头节点出发，顺着指针逐个向后跳转。链表越长，访问末尾元素的耗时越高，因此按下标访问的时间复杂度为 O(N)，天然不支持随机访问。
二、从内存管理视角看两者差异
要理解存储结构，先得搞懂我们写的代码里，数据到底存在内存的哪个区域。
前置知识：C 语言的三块核心内存区
栈区：存放局部变量、函数形参，由系统自动分配和释放，空间小、分配快。
堆区 ：由程序员手动通过 malloc / free 管理，空间大、生命周期可控，我们写的动态数据结构基本都在堆区。
静态/全局区：存放全局变量、静态变量，程序结束后由系统释放。
我们实现的动态顺序表、链表节点，数据都存储在堆区------因为它们的大小可变、生命周期需要手动控制，不适合放在栈区。
1. 顺序表的内存申请与扩容
动态顺序表通过 malloc 一次性申请一整块连续空间，空间不足时用 realloc 扩容。
整个过程是这样的：
初始申请 4 个元素的连续空间
数据放满后，申请一块 2 倍大小的新连续空间
把旧数据整体拷贝到新空间
释放旧的内存块
优点是整块管理、访问高效；缺点是扩容有数据拷贝的额外开销，且预分配的空间可能存在一定浪费。
2. 链表的内存申请与内存碎片
链表新增元素时，每次单独调用 malloc 申请一个节点的空间，用多少申请多少，没有预分配浪费，也不存在容量上限。
但频繁、零散地申请小块内存，会带来一个经典问题：外部内存碎片。
随着多次申请和释放，堆内存会被切割成大量零散的小空闲块。可能总空闲空间很大，但没有一块足够大的连续空间能放下新的顺序表，而这些零散的小空间又很难被有效利用，这就是内存碎片带来的空间浪费。
三、操作效率的真实对比：别被 O(1) 误导
很多地方会说「链表插入删除是 O(1)」，这句话其实非常容易造成误解。我们先看完整的复杂度对比表，再做澄清。
操作类型
顺序表（动态数组）
单链表
按下标随机访问
O(1)
O(N)
头部插入
O(N)（需整体后移）
O(1)
尾部插入
O(1)（扩容除外）
O(1)（带尾指针时）
中间位置插入
O(N)（元素搬移）
O(N)（查找位置）
头部删除
O(N)（需整体前移）
O(1)
尾部删除
O(1)
O(N)（无尾指针时）
按值查找
O(N)
O(N)
额外空间开销
预分配少量冗余
每个节点带一个指针
关键澄清：链表插删真的是 O(1) 吗？
严格来说，O(1) 仅指「修改指针」这一步骤，前提是你已经拿到了目标位置的节点指针。
如果需求是「在第 i 个位置插入元素」：
先遍历找到第 i 个节点的前驱：这一步是 O(N)
修改指针完成插入：这一步是 O(1)
整体时间复杂度依然是 O(N)，和顺序表处于同一量级。只有头插、已知节点位置的插删等场景，链表才能真正发挥 O(1) 的优势。
四、被很多人忽略的性能鸿沟：CPU 缓存机制
如果只看时间复杂度，两者遍历都是 O(N)，似乎性能差不多。但在真实机器上跑一遍就会发现，数组遍历的速度通常是链表的数倍甚至十几倍。
这个差距，就来自CPU 缓存。
1. 存储金字塔与局部性原理
现代计算机的存储体系是金字塔结构：
复制代码
寄存器（最快、容量最小）
↓
CPU 高速缓存（L1/L2/L3）
↓
内存 RAM
↓
硬盘（最慢、容量最大）
CPU 的运算速度远快于内存，如果每次取数据都直接读内存，CPU 会大量时间处于等待状态。为了弥补这个速度差，CPU 引入了高速缓存，并基于局部性原理预加载数据：
时间局部性：刚被访问过的数据，短时间内大概率会被再次访问
空间局部性：刚被访问过的数据，它附近的数据短时间内大概率会被访问
CPU 不会一次只读一个元素，而是一次性加载一整块连续数据（一个缓存行，通常 64 字节）放进缓存。
2. 顺序表：天生的缓存友好型结构
顺序表内存连续，完美契合空间局部性。
当你访问数组第 0 个元素时，CPU 会把它后面相邻的十几个元素一起加载进缓存。后续遍历第 1、2、3... 个元素时，直接从缓存里就能取到，不需要再访问内存。缓存命中率极高，缓存空间的利用率也非常好。
3. 链表：Cache Miss 的重灾区
链表节点在内存中离散分布，地址没有规律。
访问一个节点时，CPU 预加载的缓存行里，只有当前这一个节点是有效的，下一个节点大概率在完全不同的地址上。每访问一个新节点，都要重新从内存读取，频繁发生 Cache Miss，CPU 大部分时间都在等内存响应。
这也是为什么工程中很少用链表做遍历场景------理论上相同的时间复杂度，实际性能差距悬殊。
五、回到工程实践：为什么数组更常用？
了解了底层逻辑再回头看，就不难理解为什么主流语言的标准库里，动态数组（C++ vector、Java ArrayList）永远是最常用的线性容器：
缓存友好：连续内存带来极高的遍历与访问性能，这是绝大多数场景的刚需
实现简单：没有指针冗余，内存管理集中，出错概率低
随机访问：支持下标直接定位，适配绝大多数业务场景
链表当然也有它的适用场景，比如已知位置的频繁插删、元素数量波动极大的场景，但在日常开发中，这类场景远没有「高效存储 + 频繁访问」普遍。
六、承上启下：从通用线性表到受限线性表------栈
理解了通用线性表的优劣，再学栈和队列就会非常轻松。它们本质上都是「操作受限的线性表」------通过限制操作的位置和方式，换来更简单、更高效的特性。
以栈为例：
只允许在**同一端（栈顶）**进行插入和删除
遵循「后进先出（LIFO）」的规则
入栈（push）、出栈（pop）都只在栈顶操作
实现栈时，我们几乎都会优先选择数组（顺序栈）：
栈顶对应数组尾部，尾插尾删天然 O(1)
连续内存缓存友好，性能优秀
实现简单，没有额外指针开销
下一篇我们就动手用 C 语言从零实现一个顺序栈，拆解两种 top 指针约定的写法，以及为什么明明可以直接访问结构体成员，却还要封装成函数调用。
七、本篇总结
顺序表与链表的所有差异，根源都在「内存是否连续」：连续带来了随机访问与缓存友好，离散带来了插删灵活与无容量限制。
链表插入删除 O(1) 是有前提的，仅指修改指针的步骤；按下标插删时，查找位置的开销依然是 O(N)。
真实性能不能只看时间复杂度，CPU 缓存机制会让连续存储的结构在遍历场景下获得量级优势。
数据结构没有绝对的好坏，本质都是在时间、空间、灵活性之间做权衡，理解底层硬件逻辑，才能选对最合适的结构。
后续将继续更新队列、二叉树、哈希表与排序算法的学习笔记，代码与资料同步更新至 Gitee，欢迎交流指正。