数组模拟单双向链表：C++ 数据结构实战解析
一、链表的概念
1.1 链表的定义
线性表的链式存储即为链表。它把元素分散存放在物理上任意的位置，不像顺序表那样依赖下标维持逻辑关系。因此，除了数据本身，每个结点还需额外维护指向下一个结点的指针，这两部分合称为结点（node）。
1.2 链表的分类
常见的链表结构包括单向、双向及循环链表，它们的核心区别在于指针的指向和数量。
二、链表的模拟实现
在算法竞赛或底层开发中，使用数组模拟链表往往比动态分配内存更高效，能减少内存碎片并提升缓存命中率。我们通常用两个数组分别存储数据和指针信息。
2.1 单链表的模拟实现
2.1.1 定义与初始化
我们需要准备足够大的数组来存储数据和后继位置。变量 h 充当头指针，表示头结点的位置；id 用于为新来的结点分配下标。
const int N = 1e5 + 10;
int h; // 头指针
int id; // 下一个元素分配的位置
int e[N], ne[N]; // 数据域和指针域
// 下标 0 位置作为哨兵位
// 其中 ne 数组全部初始化为 0，其中 ne[i] = 0 就表示空指针，后续没有结点
// 当然，也可以初始化为 -1 作为空指针，看个人爱好
2.1.2 头插操作
头插是 O(1) 的操作。核心思路是让新插入元素的右指针指向哨兵位的后继，然后更新哨兵位的右指针指向新元素。
void push_front(int x) {
id++;
e[id] = x;
// 1. x 的右指针指向哨兵位的后继
// 2. 哨兵位的右指针指向 ne[h]
ne[id] = ne[h];
ne[h] = id;
}
2.1.3 遍历链表
从哨兵位的后继开始，沿着 ne 数组一直走到 0 为止。
void print() {
for (int i = ne[0]; i; i = ne[i]) {
cout << e[i] << " ";
}
cout << endl << endl;
}
2.1.4 按值查找
时间复杂度为 O(N)，适合数据量较小或无哈希辅助的场景。
