数组模拟单双向链表：C++ 数据结构实战详解
在算法竞赛或高性能场景下，频繁使用 new 和 delete 创建节点往往会导致内存碎片和时间开销过大。通过静态数组模拟链表（Array-based Linked List），我们可以用下标代替指针，既避免了动态分配的开销，又保留了链表的灵活性。
一、链表的概念
1.1 链表的定义
线性表的链式存储即为链表。它不要求物理地址连续，每个结点包含数据域和指针域。在数组模拟中，我们用两个数组分别存储数据和下一个结点的下标。
1.2 链表的分类
常见的链表包括单向链表、双向链表和循环链表。下图展示了不同结构的连接方式：
二、链表的模拟实现
2.1 单链表的模拟实现
2.1.1 定义与初始化
我们需要维护三个关键变量：头指针 h、当前分配位置 id，以及存储数据的数组 e[] 和存储后继下标的数组 ne[]。通常将下标 0 作为哨兵位，简化边界处理。
const int N = 1e5 + 10;
int h; // 头指针，指向哨兵位
int id; // 下一个可用位置的下标
int e[N]; // 数据域
int ne[N]; // 指针域，存储下一个元素的下标
注意：ne[i] = 0 表示空指针，即链表结束。
2.1.2 头插操作
头插法时间复杂度为 O(1)。核心逻辑是将新结点插入到哨兵位之后。
void push_front(int x) {
id++; // 分配新位置
e[id] = x; // 存入数据
ne[id] = ne[h]; // 新结点的后继指向原头结点后继
ne[h] = id; // 头结点的后继指向新结点
}
2.1.3 遍历链表
利用 ne 数组顺着下标跳转即可。
{
( i = ne[]; i; i = ne[i]) {
cout << e[i] << ;
}
cout << endl;
}
