关于数组模拟链表的几种情况

写这篇文章纯记录自己的想法。

1. 数组模拟单链表，题目要求模拟多个单链表的情况：
   • 第1种做法是仿照图论中经典模板《数组模拟邻接表》，用头结点数组$h[N]$表示不同的链表，只用一个下标idx用来插入元素，但这样做的缺点是：只能在头结点处前插元素，不能在任意链表中间位置插入元素，且后插入的元素会排在链表头而不是链表尾；
   • 假如要在某些链表的中间位置插入元素，必须开多个$\{e_i[],ne_i[],h_i[].idx_i\}$用来独立表示各个链表；
2. 针对第1点中缺点，想要按插入顺序输出，就需要把$h[i]$后面跟着的链表反转过来，有3种做法：
   • 最简单的做法是先把题目给的信息存下来，之后逆序遍历信息，反着建立链表中。
   • 第2种做法是先把第一个元素插入到头结点，后续结点一次插入到上一个插入结点后面，由于要在中间插入，所以必须按1.2中做法分开记录各个链表。
   • 第3种做法是建双向链表，我们从尾结点逆序向前遍历。（注意数组模拟双链表中头不能出现-1，所以头结点设置为0，尾结点设置为1。）遍历是：$for(int\quad i = r[0]; i!= 1; i=ne[i])$