戳这里：位运算降解
前言
链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
作为有强大功能的链表，对他的操作当然有许多，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。
一、预备知识
typedef 关键字：
typedef int U32;
typedef struct Student
{
int score;
char name[20];
}ST,*PST;
U32 i; //U32 i;等价 int 32；
ST student; //ST student; 等价 struct Student；
PST *pst; //PST *pst;等价struct Student *
为了方便，可以利用typedef 给某种数据类型起个别名；
二、链表
链表概念
链表属于一种离散的存储方式，离散是与连续相对的，数组是常见的连续存储方式。
链表就是一个表，表是有节点组成的。
1）n个节点离散分配；
2）彼此通过指针相连；
3）每个节点只有一个前驱节点，每个节点只有一个后继节点
4）首节点没有前驱节点，尾节点没有后继节点
链表结构
链表如下图所示
链表是由节点组成的，每个节点有两部分组成，分为数据域和指针域，数据域用来存放当前节点的数据，指针域用来存放指向下一个节点的指针变量
1）头节点：头节点数据类型与其他节点一样；是第一个有效节点之前的那一个节点；头节点并不存放数据，即数据域没有数据；加头节点的目的是方便对链表进行操作；
2）头指针：指向头节点的指针变量；
3）首节点：第一个有效节点；
4）尾节点：最后一个有效节点
5）尾指针：指向最后一个有效节点的指针变量；
如果我们希望通过一个函数对链表进行处理，我们至少需要知道链表的头指针这个参数；
链表节点类型
链表的节点其实就是一个结构体变量，在这个变量中存放当前节点的数据以及指向下一个节点的指针变量，具体见代码所示：
typedef struct node {
int data;
struct node * pnext;
}node ,*pnode;
每个节点都是一个 node 型变量，变量的 pnext成员存放的是下一个节点的地址。
插入一个节点
在没有插入节点c之前，a为b 的前驱节点（说b是c的后继节点也一样），若想在a与b之间插入节点c，只需要将a节点指针域的指针变量指向c节点，将c节点的指针域的指针变量指向b即可 。若p指向节点a，q指向节点c,进行以下操作即可完成节点插入,详情见代码
pnode t; //定义中间指针变量
t = p->pnext;
p->pnext = q;
q->qnext = t;
删除一个节点
还是首先看图
同样假设，p指针变量指向节点a，c指针变量指向节点c，若想删除节点b，将 节点a指针域的指针变量指向节点c即可，但是考虑到节约内存的效果，往往会对 p 结构体变量所占的内存空间进行释放，释放内存空间利用free()函数，另外，出于人性化考虑，在调用删除某个节点的时候，会对所删除节点的数据进行回传，以供其他需要。
看代码喽！
node t;
t = p->pnext->data; //保存节点b数据域的数据
p->next = p->next->pnext; //节点c的地址赋值给节点a的指针域的指针变量
例题：
洛谷B3631单向链表：
大家可以自己尝试一下，代码放在下面啦！
代码：
#include<iostream>
using namespace std;
const int N = 1e6+10;
int r[N];
void do1(){
int x,y;
cin>>x>>y;
r[y] = r[x];//因为是将y插入到x的右边，则y的右边数是x原来的右边数
r[x] = y;//x的右边成了y
}
void do2(){
int x;
cin>>x;
cout<<r[x]<<"\n";//输出x右边的数
}
void do3(){
int x;
cin>>x;
r[x] = r[r[x]];//因为删除了x右边的数，则当前x右边的数应该是其原来右边的数的右边的数（有点绕，但只能如此表述了）
//千万不要多写一句去改变r[r[x]]的值，因为已经没有人指向r[x]了，所以它已经被踢出来了
}
int main(){
int q;//题目给啥我用啥，这样在元素多了之后不会乱
cin>>q;
while(q--){
int d;//操作编号
cin>>d;
switch(d){
case 1 :do1();break;
case 2 :do2();break;
case 3 :do3();break;
}
}
return 0;
}
本篇就是链表的最基础讲解了（基础知识），接下来我放一个投票在下面，看下一篇讲什么。
- 搜索
- DP
- 分治
- 递归、递推
- 排序
还有什么想要的，可以在下面留言哦。
@娄辰墨
拜拜！