【原创】浅谈指针（十）链表的写法【原创】浅谈指针（十）链表

前言最近我又来更新这个系列了，其实感觉指针对于我们还是非常重要的存在。指针之所以是初学者们的“噩梦”，它的难度源于它的灵活性。
这篇文章，我想要来写一下指针的实际运用，如果指针只是一些考试的考题，那就没有意义了。最重要的，指针在C语言，乃至C++，都是不可或缺的一部分。
链表的简单回顾链表是一种数据结构。

文章图片

对于一个链表来说，每个结点有两个域，即数据域和指针域，数据域是用来存放这个链表的数字，指针域用来存放下一个结点的地址。特别的，最后一个结点的指针域设为NULL。
这样，就不需要让整个链表顺序存储了。
对于数据的插入和删除操作，链表只需要新建结点即可：

文章图片

插入和删除的时间复杂度是O(1)，不需要移动元素。而对于普通的线性表，需要移动数据，因此时间复杂度为O(n)。

文章图片

结构体声明对于链表的结构体，我们可以这样写：

typedef struct List{ int data; List *next; List(int x){ this->data=https://www.it610.com/article/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 using namespace std; typedef struct List{ int data; List *next; List(int x){ this->data=https://www.it610.com/article/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; }