零 前言
为什么放着现成的不用，要用数组来模拟链表？
原因是：这样相当于自己做了一个内存池，可以避免内存泄漏而且方便调试。更深一点来说，数组的存储位置集中，有利于提高Cache命中率。
当然，最重要的是效率原因。算法题中的数据大多十万到百万级别，如果用 new 的方法，很容易TL也就是超时。
所以掌握用数组模拟链表的方法很重要，本篇主要讲述单链表和双链表的模拟。
提示：本文为C++实现，但所有语言通用，会省略部分与实现无关的代码。会跳过一些基础概念，不了解百度即可，咱们直接看实现 ❤
一 单链表
实现
我们使用 e 和 ne 数组分别存储数据和指针，同时初始化 head 和 idx 。
const int N = 100010； // 定义常量 // e[i]表示结点i的值 // ne[i]表示结点i的next指针的指向 // head表示头结点的下标，初始为-1 // idx存储当前用到了哪个结点，也可看作指针 int e[N], ne[N]，head = -1, idx;
然后就是实现基础操作插入和删除：
// 头插法：将x插到头结点 void insert_head(int x) { e[idx] = x; ne[idx] = head; // 1.将x项指向原先的头结点 head = idx; // 2.x项为新的头结点 idx++; } // 普通插入（与头插类似）：在第k个插入的数后面插入x项，k从0开始(下同) // 先将x项指向k项的后一项，再让k项指向x项 void insert(int k, int x) { e[idx] = x, ne[idx] = ne[k], ne[k] = idx++； } // 删除第k个插入的数 void remove(int k) { ne[k] = ne[ne[k]]; // 直接将该项指针指向后一项的后一项 }
可能大家都发现了，删除结点后，我们用过的数组项不会再使用。这样的好处就是我们不需要再花时间管理内存，只要数组开大一点就可以了，速度也会更快，毕竟数组是O(1)的随机存取。同时 NULL 用-1代替，不需在意空指针异常。
// 遍历 for (int i = head; i != -1; i = ne[i]) { cout << e[i] << ' '; } 复制代码
应用
- 多个单链表（邻接表）常用于树和图的存储，树是一种特殊的图，与图的存储方式相同。
对于无向图的边ab，我们存储两条有向边 a->b，b->a，所以我们只考虑有向图的存储：
// 对于每个点k，都建一个单链表存储所有可以走到的点。 // h[k]存储每个单链表的头结点 int h[N], e[N], ne[N], idx; // 初始化 memset(h, -1, sizeof h); // 添加一条边 a->b void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++； } 复制代码
- 哈希表的拉链法
// h[k]存储每个单链表的头结点 int h[N], e[N], ne[N], idx; memset(h, -1, sizeof h); // 将x插入哈希表 void insert(int x) { int k = (x % N + N) % N; // 头插 e[idx] = x, ne[idx] = h[k], h[k] = idx++; } // 查找x是否在哈希表内 int find(int x) { int k = (x % N + N) % N; // 遍历查找 for (int i = h[k]; i != -1; i = ne[i]) if (e[i] == x) return true; return false; } 复制代码
二 双链表
实现
用 l 和 r 数组分别存储左右指针，将0作为左端点，1作为右端点，idx 从2开始：
const int N = 100010; int e[N], l[N], r[N], idx; // 初始化 void init() { r[0] = 1, l[1] = 0; idx = 2; } 复制代码
与单链表插入删除相似，我们只需要注意两个指针的指向顺序即可：
// 在第k个插入的数右边插入x项 void insert(int k, int x) { e[idx] = x; l[idx] = k, r[idx] = r[k]; // 1.将x项左右指针分别指向第k项和第k项指向的结点 l[r[k]] = idx; // 2.k项指向的结点的左指针指回x项 r[k] = idx; // 3.k项右指针指向x项 idx++; // 可如单链表一样用逗号省略为一句 } // 删除第k项 void remove(int k) { l[r[k]] = l[k]; r[l[k]] = r[k]; // 两句可以调换顺序，不会断链 } 复制代码
与单链表不同，我们实现一个插入即可实现头插、尾插、左插以及右插：
// 在链表的最左端插入数x insert(0, x); // 在链表的最右端插入数x insert(l[1], x); // 第k个插入的数左侧插入数x insert(l[k], x); // 第k个插入的数右侧插入数x insert(k, x); // 遍历, 注意i应从r[0]开始 for (int i = r[0]; i != 1; i = r[i]) { cout << e[i] << ' '; } 复制代码
三 总结
本篇思路主要来自AcWing，看完后可以去找模板题实践一下。
掌握了数组模拟链表的方法，动态链表即用类实现调用函数自然也能轻松掌握。
链表最明显的好处就是允许插入和删除表上任意位置上的节点，坏处就是不允许随机存取。
其实链表就和一般数组一样，只是他们的索引值形式不同，一般数组是有序的索引，而链表是地址值来连接的。所以我们可以将他视为一个数组，只是索引值处理不同。
