我最早接触数组模拟单链表是在需要频繁写图算法的那段时间用指针写邻接表总会遇到内存申请和释放的破事后来有人甩给我一段用数组存链表节点的代码当场就有点被击中的感觉原来链表还可以这样写既快又省心。这篇文章就专门聊聊这种实现方式。它本质上是一种静态链表用两个数组分别存数据和后继索引用head记录头节点用idx作为分配游标。它解决的痛点是在需要高频插入删除、又不想被动态内存管理拖累的场景里用数组模拟能拿到比指针链表高得多的性能代码也更好调试。适合正在学数据结构、需要写竞赛代码、或者在做嵌入式/底层存储这类“不能随便 new 和 delete”的开发者参考。1. 当链表遇上数组问题的本质是内存管理1.1 指针链表的三个麻烦很多教材一开始都会用结构体加指针来演示单链表像这样定义一个节点struct Node { int val; Node *next; };然后插入一个节点就是new Node()删除一个节点就是delete看起来自由且直观。但真到了实际项目或算法比赛中这套写法有三个绕不开的麻烦。第一个麻烦是性能不稳定。每次插入都触发一次动态内存分配而malloc和new不保证常数时间操作系统需要维护运行时堆的元数据在高频操作下可能成为明显的性能瓶颈。我曾经压测过一个需要向链表头部连续插入百万节点的程序指针版本和数组版本差了将近一个数量级原因就出在频繁分配内存上。第二个麻烦是缓存友好性差。指针链表的节点散布在堆的各个角落遍历时每次跳转都可能触发缓存未命中cache miss而这个开销往往比数据本身的读取还贵。数组模拟的节点全部集中在一块连续内存里遍历时局部性好一点执行速度自然快一些。第三个麻烦是代码复杂度。指针版除了每个节点的数据还要处理传引用和空指针。例如删除头节点和删除中间节点逻辑就不一样稍不注意就把头节点弄丢了。1.2 静态链表用下标代替指针数组模拟单链表的核心是不把“下一个节点的地址”存成指针而是存成数组下标。数组下标本身就是逻辑地址所以到处都是“索引”——而我们刚好可以通过int类型直接操纵它。用两个全局数组来模拟e[i]下标为 i 的节点的值ne[i]下标为 i 的节点的下一个节点下标如果它是链表尾就记为 -1。再用两个变量维护状态head第一个节点的下标idx下一个可以用的空闲下标。画个图的话相当于有一排抽屉每个抽屉有一个格子放数据有一个格子写下下一个抽屉的编号。head是你要从哪个抽屉开始看idx是下一个还没用过的空抽屉。整个链表不过就是顺着抽屉编号一路摸过去。这样做的好处非常明显你完全抛弃了指针运算和动态内存所有节点都自己掌控删除也不涉及真的释放内存只要把链条跳过它就行。坏处也有——提前开多少数组是你决定的如果开小了插入就会越界。所以工程上的做法是预估一个足够大的容量然后一次性静态分配。1.3 什么场景下应该直接用数组不是所有链表都要用数组模拟。普通业务里节点数量少用一个结构体指针的链表逻辑清晰很多随便怎么增删都好维护。真正适合用数组模拟的场景有三个共同特征频繁增删、大数据量、不希望依赖动态内存。比如算法竞赛里的邻接表一个图可能有几十万条边每条边都动态分配节点时间开销和内存碎片化都很难受。比如嵌入式环境里的某些缓冲区管理系统里根本没有可用的堆分配器只能用静态数组做池化。再比如一些自定义的内存池、对象池、哈希表链地址法实现底层对应的就是一个静态链表的变体。2. 核心实现四个变量和五个基础操作2.1 存储结构和初始化这里给出一套可以直接运行的C代码全程用数组模拟单链表操作包括初始化和遍历。后面每一行我都会拆开讲为什么这么写。#include bits/stdc.h using namespace std; const int N 100010; int head, idx; int e[N], ne[N]; void init() { head -1; idx 0; } int main() { init(); for (int i 0; i 5; i) { // 头插法插入 5 个数 e[idx] i; ne[idx] head; head idx; idx; } // 顺着 head 开始遍历 for (int i head; i ! -1; i ne[i]) { cout e[i] ; } return 0; }head为什么初始化为 -1因为 -1 在这里就是“空指针”的等价物。数组下标从 0 开始所以不能用 0 表示空否则会和第一个合法下标冲突。很多初学者在这里会踩坑记住在数组模拟的链表里-1才是链表的终结标记。idx为什么要从 0 开始因为它表示“下一个可用的数组下标”从 0 开始意味着我们按顺序使用数组空间。插入第 0 个节点用下标 0插入第 1 个用下标 1如此类推。idx本质上像一个极简的内存分配器指针每次分配一个下标就自增 1。它不代表链表长度只代表已经使用到哪个位置了。2.2 头插法为什么 O(1) 这么香头插法就是把新节点插到链表最前面。代码只有短短几行void add_to_head(int val) { e[idx] val; ne[idx] head; head idx; idx; }每一步都说明一下。第一步e[idx] val把新数据放进下一个空闲抽屉里。 第二步ne[idx] head让新抽屉指向原来的头节点也就是让新节点先续上整条链。 第三步head idx更新链表头让头变成新节点。 第四步idx分配游标向前推进表示这个抽屉已经“占用”了。这种操作完全不需要移动任何已有数据只需要改几次下标所以是 O(1)。实际工程里如果要反复在链表头部加数据比如哈希表的链地址法、图邻接表的建边头插是效率最高也最好写的。我特别建议新手建图的时候无脑用头插跑起来完全不用担心顺序问题因为遍历时自然就是逆序而大部分算法根本不在乎边的遍历顺序。2.3 在指定节点后插入有时不是插在头部而是在已知某个节点后面插入新值。这时我们需要知道“哪个节点”的下标记为 k。操作几步void insert_after(int k, int val) { e[idx] val; ne[idx] ne[k]; // 新节点接管 k 原来的后驱 ne[k] idx; // k 的后驱改成新节点 idx; }看到了吗插入逻辑和指针链表其实一模一样只是把next换成ne[k]。顺序绝对不能反先让新节点指向ne[k]再让k指向新节点。如果反过来先修改ne[k]原来的链表后半段就找不到了等于丢了一个分支。有一个细节要注意这里的“指定节点”一般指的是下标 k而在实际算法题里给你的常常是“从 1 开始数的第 k 个节点”。如果只存了head你就得先遍历找到这个节点的下标再执行插入。有些题有额外的操作序号特别容易搞混建议画个图。2.4 删除操作逻辑删除才是精髓删除指定节点 k 的后一个节点void remove_after(int k) { ne[k] ne[ne[k]]; }这行代码表示让 k 的下一个节点跳过直接指向下下个节点。比如链表是 A - B - C我们删掉 B就等价于让 A 的后继变成 C。注意这里根本没释放内存数组里那个被删的位置还存着旧数据和旧指针只是没有任何一个节点再指向它它就等于“从链表里消失”了。这就是逻辑删除也是数组模拟法最有意思的地方。删除头节点就特殊一些因为头节点没有前驱不能用上面的方法。正确写法是void remove_head() { head ne[head]; }很多初学者在写删除操作时会忘记处理“待删除节点是头节点”的情况导致链表头丢失。别问我是怎么知道的调试两个小时后你会感受到这条经验的价值。3. 原理拆解静态分配、游标推进和边界条件3.1 idx 就是一台极简内存分配器如果你接触过操作系统里的内存管理会发现这里的idx就是一台极简的内存分配器。它只干一件事每次当前空闲地址 1 返回出来没有任何回收机制。因此数组模拟的链表天然适合“只增不减”的场景或者删除节点之后也不打算重新使用这些下标的情况。在算法题里这完全不是问题因为题目的操作总数是有限的开一个够大的数组就能保证不越界。但如果真的想在同一个数组上回收再利用被删除节点的下标那就需要额外维护一个“空闲下标栈”或“空闲链表”。每次删除时把下标入栈每次插入时优先从栈里取。这个思路在后来的内存池设计里很常见但平时写链表完全不需要这么复杂idx一路推进就够了。3.2 边界条件head、-1、数组容量数组模拟链表有三个边界条件需要烂熟于心。第一个是链表为空或遍历完毕。判断条件是i -1。在数组模拟中遇到 -1 就代表“到头了”不要再继续访问下去。第二个是插入前检查数组是否越界。如果你开了N的数组但实际要插超过 N 个节点就会导致e[idx]下标越界。这个错误在本地运行时可能报错也可能带崩程序。一个常用的做法是在插入函数开头断言idx N或者统一把N设成“理论最大操作数 10”留点余量。第三个是插入和删除操作的目标下标合法性。如果 k 已经是链尾insert_after时ne[k]本身是 -1插入没问题新节点会变成链尾但remove_after时ne[ne[k]]会访问ne[-1]这就是数组下标越界。所以删除之前一定要判断k是否存在后继节点。代码里建议写成bool remove_after(int k) { if (ne[k] -1) return false; ne[k] ne[ne[k]]; return true; }3.3 为什么数组模拟之后遍历这么快很多人看了代码会有疑惑这不就是把指针换成了下标吗为什么更快除了前面说的减少动态内存分配还有一个重要原因是数组的“连续内存”和 CPU 缓存局部性。链表的节点本质上是一个一个离散的对象一个接着一个被访问如果是数组存储这些节点在内存里彼此相邻CPU 一次加载一个缓存行通常 64 字节就能把接下来好几个节点都带进来。而动态分配的结构体节点内存分布随机CPU 每次都要重新把数据从主存拉到缓存里来这就是缓存命中率和内存带宽上的差距。在数据量小的时候差距不明显但当链表长度达到几十万甚至上百万时数组模拟的遍历性能通常是指针链表的 2 到 4 倍如果操作本身还包括反复分配和释放内存差距还能更大。这也是为什么许多要求高性能的底层库都倾向用“对象池索引”来代替裸指针链表。4. 三种链式存储方案横向对比4.1 数组模拟 vs 结构体指针 vs 顺序表 vector很多时候我们需要做出选型判断。我把三种常见方案放到一张表里对比注意这里的“顺序表 vector”和“链表”是两种完全不同逻辑的结构但很多人实现的时候拿不准该用哪个。对比维度数组模拟链表静态链表结构体指针链表vector / 动态数组插入头部O(1)极快O(1)但需分配内存O(n)需要搬移元素删除指定节点O(1)跳过即可O(1)需要释放内存O(n)需要搬移元素内存占用紧凑每节点约 8-16 字节较高含指针对齐与堆管理开销紧凑但扩容可能浪费空间分配与回收无动态分配完全静态每次 new / delete动态扩容均摊 O(1)缓存友好性高数组连续存储低节点散落很高连续存储代码调试直观下标打印即可指针难追踪容易悬空最简单但增删头部慢适用场景算法题、内存受限、图邻接表通用业务、节点结构复杂读多写少、按位置访问结论很清晰如果你的需求是频繁头部插入、频繁删除、追求极致性能且节点结构简单优先选数组模拟链表。如果你更在意代码可读性、节点字段很多、项目周期长结构体指针链表更自然。如果你的核心操作是按下标随机访问而不是频繁在头部增删直接上 vector 就是了。4.2 怎么选才不踩坑有一个要避免的误区是“用 vector 也能实现头部插入为什么还要学数组模拟”因为 vector 头插是 O(n)如果你循环一百万次头插就是十亿次元素移动直接卡死。数组模拟链表是 O(1)能稳稳扛住高频操作。但也要避免另一个极端明明数据量很小、节点逻辑复杂、根本不需要优化却用数组模拟然后用几个索引指针把自己绕晕。这时候用普通指针链表代码短得多也更好维护。技术选型没有绝对的好只有相对场景合适。我个人判断标准就三条操作频率高不高、是否担心动态分配开销、代码容不容易出问题。三条里占两到三条就值得用数组模拟一条都不占老老实实写普通链表。5. 四个高频应用场景从哈希表到邻接表5.1 哈希表链地址法每个桶挂一条链表哈希表处理冲突最经典的方式就是链地址法每个桶其实就是一个链表头。插入的时候先通过哈希函数算出桶编号再把元素挂到桶对应的链表上这个链表完全可以用数组模拟。具体做法是桶数组存的是链表头的下标链表的节点数组和ne数组全局共用。需要插入时idx给新节点分配位置然后修改对应桶的head和ne。删除同理。用数组模拟的好处在于哈希表扩容时你可以整体重新计算和搬运不需要对堆里的节点一个个做深层复制直接操作下标即可。很多需要极致性能的哈希表就是这么做的而不是用 C STL 里的list。当然工程上直接用unordered_map更方便但你自己实现一个定制的哈希表时静态链表就是很好的底层结构。5.2 图的邻接表建图算法的标配写图论算法时无论是深度优先搜索还是最短路径都要把图存起来。用数组模拟邻接表是非常美的一种做法。每条边只是一个节点节点里存的是“终点顶点编号”和“下一条边的下标”。建图时用头插法把每条边插入到以起点为头节点的链表里。这样建图复杂度是 O(边数)遍历某个点的所有出边也只是沿着对应链表走一遍。int h[N], e[N], ne[N], idx; void add(int a, int b) { e[idx] b; ne[idx] h[a]; h[a] idx; idx; }这段代码可能就是众多算法教材里最简短的建边代码了。h[a]存的是顶点 a 的第一条边下标每次插入新的边都让它成为新的第一条边。遍历的时候for (int i h[a]; i ! -1; i ne[i]) { int b e[i]; // 这是 a 的一个邻接点 }这种写法省去了结构体、完全避免内存泄漏在竞赛和底层实现中都是首选。如果你去读一些高性能开源图的存储实现很多核心结构都和这个不谋而合。5.3 内存池的雏形回收与不回收之间的权衡前面说过数组模拟链表删除节点时并不真的释放内存。这在很多场景下反而是一种优势。反复分配和释放内存的时间开销经常大于直接复用内存尤其是在嵌入式系统和游戏引擎里每帧都要频繁创建和销毁对象如果每次都走系统堆分配器帧率直接拉胯。所以很多内存池的实现思路是预先分配一块大内存用静态链表维护空闲块链表分配就是从空闲链表头弹出一个块回收就是把块头插回空闲链表。你看这不就是数组模拟链表最经典的玩法吗空闲链表的“空指针”就是 -1分配就是改head回收也是改head全程 O(1)。其实数据结构教材里的静态链表到了真正工程里就是各种内存池和对象池的骨架。你掌握了数组模拟之后再去看内存池源码会发现整个思路清清爽爽一点都不神秘。5.4 极简 LRU 雏形维护访问顺序LRU 缓存淘汰策略里经常用一个双向链表维护“最近使用”的顺序。虽然双向链表需要两个方向的指针但退化到单链表时如果我们只关心“最近访问的放在头部最久没访问的在尾部”用数组模拟单链表配合一个哈希表存键值到下标的映射也能做一个能跑的简化版。思路是每次访问某个数据如果命中就把这个节点从原位置拆下来采用“逻辑删除头插”的方式移动到链表头如果缓存满了就删除链表尾。当然严格意义的 O(1) 移动还需要双向链表但单链表在理解 LRU 的核心思想时已经足够用了。你只需要知道数组模拟的方式完全可以支撑这种高频操作而不产生内存碎片就够了。6. 常见问题与排查实录6.1 三个最容易踩的坑第一个坑是遍历的时候写成for (int i head; i ! NULL; i ne[i])这在指针链表里没问题但在数组模拟里NULL可能就是 0而合法下标 0 被当成空链表终止了于是链表刚插入元素就不显示。记住统一用 -1 表示空。第二个坑是删除后忘记维护head。假设链表[3, 5, 7]你想删除头节点 3如果用remove_after(head)而不是head ne[head]最后得到的链表是 [5, 3, 7] 这种错乱结构因为原来的链头还指向 5你把 3 的 next 指向 3 的 next 的 next相当于把 5 跳过了。这非常容易搞混排查时可以先打印 head 的值和各个节点的 e、ne。第三个坑是数组下标越界。这个不太容易当场发现因为访问ne[-1]时你得到的可能是一个随机值而不是立即崩溃。调试方法是用断言或者每次操作前打印 idx。我在竞速开发中通常会在关键操作前检查idx N不要硬等到栈溢出或者段错误出现。6.2 调试方法快照打印比断点好用指针链表调试时你想看链表状态得一层层展开指针很麻烦。数组模拟链表调试就舒服多了直接把整个数组打出来看就行。以下是常用的调试函数把所有节点的下标、值和后继打出来void debug() { printf(head%d idx%d\n, head, idx); for (int i head; i ! -1; i ne[i]) { printf([%d]e%d ne%d - , i, e[i], ne[i]); } printf(NULL\n); }如果你怀疑链表形成了环就在打印的时候加个计数器超过节点总数就停下来立刻输出“疑似成环”。这个技巧帮我排过很多隐藏的指针错位问题。6.3 常见问题速查表现象可能原因解决方法链表刚插入元素但遍历为空head被初始化为 0 或忘记初始化head初始化成 -1且 init 后确认执行遍历中途卡死或打印非常长出现了环某个 ne 指回前面的下标打印快照检查插入时是不是先改了 ne[k]删除节点后数据错乱头节点删除时用了通用删除函数删除头节点用head ne[head]插入过程崩溃或数组越界N 开小了或 idx 超出数组范围增大 N或在插入函数中检查 idx N删除链尾时报越界ne[ne[k]]中的 ne[k] 为 -1删除前判断if (ne[k] -1) return打印结果顺序不对头插后按插入顺序理解输出头插是先到先插入的位置输出是逆序属正常7. 扩展思路沿着这个方向再走远一点7.1 从单链表到双向链表如果你理解了数组模拟单链表自然会想知道如何模拟双向链表。做法是加一个数组存前驱比如pre[i]同时维护head和tail。删除和插入多改一个方向就行。这种结构在内存池和 LRU 中很常见。7.2 从静态分配看整个数据世界的取舍数组模拟链表背后的哲学其实就是在有限资源下用“空间连续性”换取“操作确定性”。动态内存灵活但它昂贵且不可预测。静态数组粗暴但它稳定并且速度快。真正的工程师要在两者之间找到平衡点。如果你接下来要写自己的哈希表、邻接表、内存池建议都从数组模拟的思路出发。提前想清楚内存生命周期能省下大量用 Valgrind 查泄漏的夜晚。我自己在刚开始接触数组模拟链表的时候犯过的最大一个错误就是忘记维护head导致一整条链在删除头节点之后变成两条不相干的片段排查了两小时才醒悟。后来养成一个习惯每一次插入和删除操作都先想想“head 会不会变”再想想“idx 被消费的位置会不会越界”两个问题都能答上来这份代码基本就稳了。最后再分享一个小技巧如果你担心自己写的数组模拟链表边界条件出错可以准备一小组测试命令专门覆盖空链表插入、删除唯一节点、在最后一个节点之后插入、删除链尾四种情况。把这四种情况测试通过绝大部分问题都会提前暴露出来而不是等到一个更大的项目里才爆雷。