数组模拟链表用预分配静态池替代new/delete，避免内存碎片与分配开销，提升缓存局部性；需用int下标代替指针，以-1为空指针，维护空闲链表实现O(1) alloc/free。
为什么用数组模拟链表节点而不是直接 new？
在嵌入式、竞赛或内存受限场景下，频繁调用 new 和 delete 会带来分配开销和碎片风险。数组模拟（也叫“静态链表”）把所有节点预分配在连续内存中，用整数下标代替指针，规避动态分配，还能提升缓存局部性。
常见错误是直接套用指针版逻辑却忘了下标边界检查，比如用 -1 表示空指针，但忘记初始化或越界访问 next[i]。
使用时注意三点：
- 所有“指针”字段（如 next、prev）必须是 int 类型，存的是数组下标而非地址
- 空节点统一用 -1 表示（不能用 0，因为下标从 0 开始）
- 必须维护一个空闲链表（free list），记录哪些下标尚未被占用，否则无法高效回收节点
如何定义结构体并初始化静态池？
核心是把链表节点的字段平铺进结构体，再用数组承载：
struct Node {
int val;
int next; // 下标，不是指针
int prev; // 可选，双向时需要
};
<p>const int MAXN = 100005;
Node pool[MAXN];
int head = -1; // 当前链表头节点下标
int free_head = 0; // 空闲链表头下标（初始时整个数组空闲）</p><p>// 初始化空闲链表：pool[i].next = i+1，pool[MAXN-1].next = -1
for (int i = 0; i < MAXN - 1; ++i) {
pool[i].next = i + 1;
}
pool[MAXN - 1].next = -1;
容易踩的坑：
立即学习“C++免费学习笔记（深入）”；
- 忘记初始化
free_head或误设为-1，导致后续alloc()返回非法下标
- 混淆
head（数据链表头）和free_head（空闲链表头），二者独立维护
-
MAXN设太小，运行时下标越界不报错但行为未定义（尤其在 Release 模式下）
怎么实现 alloc / free 而不泄漏？
alloc() 从空闲链表取一个节点，free(i) 把下标 i 插回空闲链表头部（O(1)）：
int alloc() {
if (free_head == -1) return -1; // 池满
int idx = free_head;
free_head = pool[free_head].next;
return idx;
}
<p>void free(int idx) {
pool[idx].next = free_head;
free_head = idx;
}
关键点：
-
alloc()不负责初始化val或prev，调用方必须显式赋值，否则残留脏数据
-
free(i)前必须确保i是之前alloc()返回的有效下标，否则破坏空闲链表结构
- 如果支持多线程，这里需要加锁——但多数静态链表场景默认单线程
插入/删除操作和指针版有何不同？
逻辑一致，只是所有“指针移动”变成“下标跳转”。例如头插：
int new_idx = alloc(); if (new_idx == -1) return; // 分配失败 pool[new_idx].val = x; pool[new_idx].next = head; head = new_idx;
删除头节点：
if (head == -1) return; int old_head = head; head = pool[head].next; free(old_head);
易错细节：
- 删除时没调用
free(old_idx)→ 内存泄漏（虽然是静态池，但空闲链表变短，后续 alloc 可能提前失败）
- 修改
next顺序错误，比如先改head = pool[head].next再取old_head，结果丢失原节点下标
- 双向链表中修改
next后忘了同步更新后继节点的prev字段，导致遍历断裂
数组模拟链表真正难的不是写法，而是时刻意识到：你操作的不是地址，是下标；不是堆内存生命周期，是池内索引的归属权。一旦混用 new 和数组下标，或者跨池复用下标，调试会非常隐蔽。
