数组模拟链表

优点

高效：插入、删除操作十分简便，不需要像指针链表一样遍历

**

声明变量

head：头节点 e[i]：节点i的数值 ne[i]：节点i的next指针 idx：存储当前用到了几个节点

int head, e[N], ne[N], idx;

**

初始化

void init() { head = -1; // 指针值为 -1，表示到了链表末尾，无节点 idx = 0; }

**

向表头插入数

void head_to_inst(int x) { e[idx] = x; ne[idx] = head; head = idx ++; }

**

插入

调用该函数：inst(k - 1, x); //在第k个输入的数后面插入一个数x

注意:第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

void inst(int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx ++; }

**

删除

调用该函数：

cin>>k; if(!k) head = ne[head]; else delt(k - 1);

// 删除第k个输入的数后面的数（当k为0时，表示删除头结点）

注意:第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

void delt(int k) { ne[k] = ne[ne[k]]; }

**

遍历

for (int i = head; i != -1; i = ne[i]); printf("%d ", e[i]);

参考资料：acwing 数组模拟单链表