单链表
介绍
链表是用来存储具有相同性质的数据的集合，每个具有该性质的数据单位成为节点(Node)。
单链表的定义
单链表具有两项基本要素，单链表内的数据项val和后驱节点next，因此最简单的单链表节点的结构体定义为：
struct Node{ // 节点定义
int val; // 单链表内存储的数据项
Node *next; // 后驱节点，指向下一个节点
};
为什么要用数组模拟链表
我们知道用结构体实现链表时我们创建新节点需要用到new，例如：
Node A = new Node(NULL);
它表示创建一个节点，并把它赋值为NULL。但是new这个操作非常耗时，我们做题时用结构体容易超时，数组显然会快很多。
如何用数组模拟
节点中有值val和next指针，显然用一个数组是无法完成的。因此我们需要一个存入值val的数组e[N]，一个存入next指针的数组ne[N]。当然有了这些还不够，因为如果我们要创建节点时并不知道哪个数组下标被用过，哪个没被用过，因此我们需要一个标记当前可用的数组下标的变量idx，我们还需要一个头结点head。
int head,e[N],ne[N],idx; // 数组模拟链表所需的变量
我们可以将idx看成一个节点，而e[idx]则存入该结点存储的值val，ne[idx]存储该点的next指针,head指向的是链表头。
那么还有一个问题，如何表示NULL呢？我们默认将-1看成NULL。
链表的基本操作
链表的创建
创建链表时，我们只需要将头结点指向NULL，并将节点初始化为0即可。
void init(){
head = -1; // 头结点指向空
idx = 0; // idx初始化为0
}
链表的插入
假设我们要给链表用头插法插入一个val = a的节点，此时我们需要创建一个新节点idx(由于idx表示的是当前可用的数组下标，因此可默认为已创建新节点)。
void add(int x){ // 头插法
e[idx] = x; // 将节点赋值为x
ne[idx] = head; // 节点的next指针指向头结点next指针指向的节点
head = idx ++; // 链表头指向插入的节点，可用的节点下标 + 1
}
链表的删除
假如要删除头节点，只需要将head指向的节点更新为head指向的节点指向的节点即可。
void remove(){ // 删除头结点
head = ne[head];
}
还有一些比较不常用的操作就不细说了，只要使用这个数组模拟链表的思想，其它做法也是很容易推出来的。
例题
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第
k个插入的数后面的数； - 在第
k个插入的数后插入一个数。
现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数M，表示操作次数。
接下来M行，每行包含一个操作命令，操作命令可能为以下几种：
- H x，表示向链表头插入一个数 x。
- D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
- I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1
≤
M
≤
100000
1≤M≤100000
1≤M≤100000
所有操作保证合法。
输入样例：
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例：
6 4 6 5
解题思路
操作1：向链表头插入一个数
在上面已经讲过头插法，不再赘述
操作2：删除第k个插入的数后面的数
与删除头结点类似，因为ne[k - 1]是指向k的，因此只需要ne[k-1] = ne[ne[k - 1]];即可。
操作3：在第 k 个插入的数后面插入一个数 x
与头插法类似，只不过要将head换成ne[k]，表示将新节点的next值指向第k个插入节点的next指向的节点，再将节点k的next指针指向新节点。
代码
#include<iostream>
using namespace std;
const int N = 100010;
int head,e[N],ne[N],idx;
void init(){ // 初始化
head = -1;
idx = 0;
}
void add_to_head(int x){ // 头插法
e[idx] = x;
ne[idx] = head;
head = idx ++;
}
void add(int k,int x){ // 在第 k 个插入的数后面插入一个数 x
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx ++;
}
void remove(int k){ // 删除第k + 1个插入的数后面的数
ne[k] = ne[ne[k]];
}
int main(){
int n;
cin >> n;
init();
while(n --){
int k,x;
char op[2];
scanf("%s",op);
if(op[0] == 'H'){
cin >> x;
add_to_head(x);
}
else if(op[0] == 'I'){
cin >> k >> x;
add(k - 1,x);
}
else {
cin >> k;
if(!k) head = ne[head]; // 假如k == 0，则删除头结点
remove(k - 1);
}
}
for(int i = head; i != -1; i = ne[i]) cout << e[i] << ' '; // 将链表输出
return 0;
}