最近我又来更新这个系列了，其实感觉指针对于我们还是非常重要的存在。指针之所以是初学者们的“噩梦”，它的难度源于它的灵活性。
这篇文章，我想要来写一下指针的实际运用，如果指针只是一些考试的考题，那就没有意义了。最重要的，指针在C语言，乃至C++，都是不可或缺的一部分。
链表是一种数据结构。
对于一个链表来说，每个结点有两个域，即数据域和指针域，数据域是用来存放这个链表的数字，指针域用来存放下一个结点的地址。特别的，最后一个结点的指针域设为NULL。
这样，就不需要让整个链表顺序存储了。
对于数据的插入和删除操作，链表只需要新建结点即可：
插入和删除的时间复杂度是O(1)，不需要移动元素。而对于普通的线性表，需要移动数据，因此时间复杂度为O(n)。
对于链表的结构体，我们可以这样写：
typedef struct List{
int data;
List *next;
List(int x){
this->data=x;
next=NULL;
}
};
List *lst;
data是数据域，next是指针域。
其中，List(x)是一个构造函数，这样在使用new进行结点分配的时候可以简便书写。分配的时候就需要这样写：
l=new List(x);
这个构造函数做了两件事：一个是把data进行赋值，一个是把next设为NULL。
补充1：this指针
其中，写this->data，this是指这个结构体本身，例如调用：
l=new List(x);
此时this就指向l。this是一个特殊的指针。有一种形象的比喻方式：
当你进入一个房子后，你可以看见桌子、椅子、地板等，但是房子你是看不到全貌了。
对于一个类的实例来说，你可以看到它的成员函数、成员变量，但是实例本身呢？
this是一个指针，它时时刻刻指向你这个实例本身。
当然，这里不写this也是可以的。这只是写法问题。
补充2：->运算符
这个运算符，我们一般称为“箭头运算符”。
假设我们有现在下面的一个结构体：
struct info{
string name;
int age;
}
如果现在有一个普通变量x，那么引用其中的age，写作：x.age
如果现在有一个指针变量p，那么引用其中的age，要写作p->age
也就是说，对于一个指针结构体，引用其中的成员需要使用->运算符。
本质上，p->age等同于(*p).age，注意这里括号虽然麻烦但是不可省略。箭头运算符只是一种简便写法。
我们知道，如果一个链表的当前结点为NULL，那么它必定是最后的结点。因此，我们可以采用递归的写法，如果链表当前节点不为NULL，那么就下一个结点。
void add(List *&l,int x){
if(l==NULL){
l=new List(x);
return;
}
else add(l->next,x);
}
l=new List(x);，之前说过的构造函数写法。
add(l->next,x)表示找下一个结点。
补充3：*&是什么鬼！
我们知道，&是引用传递参数。我之前的浅谈指针（三）写过，网页链接如果懒得在原文找的话，我这里直接把原文贴出来了：
在这里，*表示指针，&表示引用传递，那么加在一起就是指针的引用传递，虽然声明看上去很烦，但是理解了也就是这么回事。
输出链表的所有元素毫无难度的函数，我直接贴出来了，逻辑和add函数类似。
void write(List *l){
if(l==NULL)return;
else{
printf("%d ",l->data);
write(l->next);
}
}
链表的灵活之处就是它的插入和删除函数。
如下图所示，我们要在2之后插入一个10：
首先，我们需要把10和3连接起来，否则一旦断掉2和3之间的连接，那么整个链表就直接分离了，无法再找到3的位置。
下一步，就是把2和10连接起来，同时断开2和3的连接。
这样就把插入的操作完成了，其实本质是很简单了。
void insert(int pos,List *&l,int x){
if(pos==1){
List *p=new List(x);
p->next=l->next;
l->next=p;
}
else insert(pos-1,l->next,x);
}
为了找到待插入的位置pos，我们可以采用递归的方法，每往后一个结点pos-1，最终当pos=1时就到了想要的位置。
删除元素同样的链表，假设删除其中的3：
首先，先新建一个指针，指向3，否则后续操作过后就无法释放这块内存：
第二步，把2连接到4上面去。
最后，释放这个新建的指针，本质就是释放3。
代码还是一样，注意最终到pos=2就要停止了，这个算法无法删除首个结点的位置。
void remove(int pos,List *&l){
if(pos==2){
List *p=l->next;
l->next=l->next->next;
delete p;
}
else remove(pos-1,l->next);
}
一套完整的链表写下来也是有四五十行代码的，完整代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef struct List{
int data;
List *next;
List(int x){
this->data=x;
next=NULL;
}
};
List *lst;
void add(List *&l,int x){
if(l==NULL){
l=new List(x);
return;
}
else add(l->next,x);
}
void write(List *l){
if(l==NULL)return;
else{
printf("%d ",l->data);
write(l->next);
}
}
void insert(int pos,List *&l,int x){
if(pos==1){
List *p=new List(x);
p->next=l->next;
l->next=p;
}
else insert(pos-1,l->next,x);
}
void remove(int pos,List *&l){
if(pos==2){
List *p=l->next;
l->next=l->next->next;
delete p;
}
else remove(pos-1,l->next);
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
add(lst,x);
}
while(m--){
int k;
scanf("%d",&k);
if(k==1){//插入操作
int pos,val;
scanf("%d%d",&pos,&val);
insert(pos,lst,val);
write(lst);putchar('\n');
}
else if(k==2){//删除操作
int pos;
scanf("%d",&pos);
remove(pos,lst);
write(lst);putchar('\n');
}
}
return 0;
}