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

Python微信订餐小程序课程视频

https://edu.csdn.net/course/detail/36074

Python实战量化交易理财系统

https://edu.csdn.net/course/detail/35475

前言

最近我又来更新这个系列了，其实感觉指针对于我们还是非常重要的存在。指针之所以是初学者们的“噩梦”，它的难度源于它的灵活性。
这篇文章，我想要来写一下指针的实际运用，如果指针只是一些考试的考题，那就没有意义了。最重要的，指针在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
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;
}