链表
题单介绍
平时我们在定义多个变量时一般使用数组。
数组有个很大的优点，那就是想要取第几个变量就能取到第几个变量。
但是数组也有一个缺点，那就是在数组中间插入或者删除一个变量时，要把后面的所有变量都往后或往前挪一位，才能插入或者删除。
那么这个挪移的时间就会很慢，数组有多长，就可能要移多少个变量。
那么有没有方法能使插入和删除变快呢？
在写语文作文时，写完后发现中间少了一个字。那应该怎么把字插入进去？
可以把要插入的字写到另外的地方，然后做个标记表示应该插入到哪里。
那么我们能不能在插入变量的时候把变量放到其他地方，再做个标记呢？
对于每个变量a[i]，再用nxt[i]记录一下他的下一个数所在的位置。
也就是说，**对于每个数，记录它下一个数所在的位置。那么这种数据结构就叫做链表。**
一般来说，链表的一个整体会用一个结构体来表示
```cpp
struct node{
int value;//记录该节点的值
node* nxt;//记录下一个节点所在的地址
};
```
不过由于在竞赛中指针很少使用，所以一般nxt记录的是下一个点在数组里的位置，而不是在内存里的地址。
所以结构体定义稍微改一下：
```cpp
struct node{
int v;
int nxt;
};
node a[100];//定义若干节点备用
int cnt;//记录已经数组里前面多少个节点已经被使用了
int head;//记录这个链表的第一个元素所在的位置
遍历整个链表：
for(int i=head;i!=0;i=a[i].nxt){//0表示链表结束
//语句
}
插入节点：
void insert(int x,int y){//在第x个节点后面插入一个值y
cnt++;
a[cnt]=y;
a[cnt].nxt=a[x].nxt;
a[x].nxt=cnt;
}
删除节点：
void del(int x){//删除第x个节点后面的节点
a[x].nxt=a[a[x].nxt].nxt;
}
```
上面这段代码就是单链表的插入、删除和遍历了。
除了只能从前往后遍历的单链表，还有双向链表和循环链表。
双向链表指的是每个节点不仅记录下一个节点的位置，还记录上一个节点的位置。
循环链表指的是链表的尾部不会指向0，而是指向链表的第一个元素。
这两种链表对应的插入、删除和遍历代码都需要相应的修改。具体如何修改可以自行尝试。