【数据结构初阶】 --- 单链表

关于链表你应该先了解这些

下图描述了物理模型和逻辑模型，大多数常见的其实是逻辑模型，但这对初学者或者掌握不扎实的同学不太友好，所以这里我重点讲解物理模型，当了解了这些细节，以后做题或是什么就直接画逻辑模型就好了

物理模型：
在这里，一个大方框表示着一个结点，这个结点里存储了两种数据：

• 一是你本身要存储的数据
• 二是为了让这些结点具有连接作用，而需要存放相应结点的地址，这样，当你访问了当前的结点内容，想要访问下一个结点的内容，这时就需要有下一个节点的地址，这就是为什么要存地址的原因。

链表的类型

单链表

上面的就是单链表

双链表

与单链表的不同就是一个结点里存有两个地址，可以实现双向访问，弥补了单链表只能单向访问的缺点

循环链表

单链表的最后一个结点存的是NULL，而循环链表的最后一个结点存放的是第一个结点的地址，事实上，你看这张图，确实也分辨不出哪个是第一个结点，所以想象成单链表最后一个结点放的头结点的地址就行

链表的存储方式

数组是一块连续的内存，而链表不同，每个结点都有自己的地址，并没有联系，这些地址是取决于操作系统的内存管理（在没学习操作系统之前可以当做这些地址是随机分配的）

链表的定义

这一节，我所讲的知识都是基于单链表

typedef int SLTDataType;//结点中存储数据的类型
typedef struct SListNode
{
	SLTDataType data;//结点中要存储的数据
	struct SListNode* next;//结点中指向下一个结点的指针
}SLTNode;

先看这张图：

与开头的那张区别就在于头指针phead，这是一个指针变量，用来存放第一个结点的地址，利用该指针就可以依次访问或操作节点中的数据
接下来初始化一个指向结点的头指针：（这里是头指针，不是头结点）

SLTNode* phead = NULL;

链表的操作

先了解是如何访问链表的

完整流程：

为什么要用二级指针？

经过了头插操作，我们将new_node成功连入链表的头部，pphead存的也是new_node的地址，但是，我们的实参phead，它里面的内容竟还是之前第一个结点的内容，而往后我们还是要用phead来访问操作这个链表但新插入的节点却永远访问不到，那你说能不能用pphead访问不就行了，记住，pphead是局部变量，执行完头插这个函数pphead就不存在了，我们想操作这个链表，一直都是利用phead当做实参传递的。想要改变实参的内容只需传址调用即可，因此，我们将指针变量phead的地址当做实参传递过去，那么相应的，形参就需要一个二级指针接收，因为phead是指针，我们传递的是指针的地址，所以需要二级指针接收。如此，通过对二级指针pphead解引用就可以直接对phead的内容进行修改，到此，phead就可以存new_node地址了

创建一个新节点

SLTNode* SLTCreatNode(SLTDataType x)
{
//里用malloc函数向栈区开辟一个大小为sizeof(SLTNode)个字节的空间，将这个空间的首地址存放于new_p这个指针变量中
	SLTNode* new_p = (SLTNode*)malloc(sizeof(SLTNode));
	malloc函数开辟空间失败会返回NULL，这时就不要再进行后续操作，避免解引用空指针
	if (new_p == NULL)
	{
		perror("malloc");//进行报错，在屏幕上会出现错误提示
		exit(0);//直接让程序结束
	}
	//开辟成功就将x存入新的节点中，节点中的指针next指向NULL
	new_p->data = x;
	new_p->next = NULL;
	return new_p;
}

打印链表

这里只需将头指针的内容作为实参穿过来，利用形参指针phead接收就能达到效果

void SLTPrint(SLTNode* phead)//这里接收的是第一个结点的地址
{
	while (phead != NULL)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

头插法

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead != NULL);

	SLTNode* p_node = SLTCreatNode(x);
	p_node->next = *pphead;
	*pphead = p_node;
}

尾插法

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	//pphead里存的是phead的地址，不可能为NULL，所以如果传来NULL就会出问题，因此需要防止误传NULL指针，这里就要断言一下
	assert(pphead != NULL);

	SLTNode* p_node = SLTCreatNode(x);

	//试着将空链表的逻辑带入else中，你会发现cur->next在访问空指针，这是不行的，所以要专门为链表为空这个特殊情况写一段代码
	if (*pphead == NULL)
	{
		*pphead = p_node;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = p_node;
	}
}

头删法

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead != NULL);
	assert(*pphead != NULL);//如果传来的是个空链表就报错

	SLTNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
}

尾删法

//尾删的时候分三种情况讨论，没有节点，一个节点，多个节点
//不是说上来你就知道要分三种情况，而是当你写出适应多个节点的代码后
//这时你就要考虑边界情况，没有节点或者一个还是两个节点的情况
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead != NULL);
	assert(*pphead != NULL);//头指针为空（没有节点）就报错

	if ((*pphead)->next == NULL)//只有一个节点的情况
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		SLTNode* cur = *pphead;
		SLTNode* prev = NULL;
		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
	}
}

给指定的地址插入数据

这里是要将数据插入到pos前，为什么我们会知道一个结点的地址pos呢，答案就是查找函数帮你找的

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead != NULL);
	assert(pos != NULL);
	assert(*pphead);//传过来头指针指向的是空

	SLTNode* p_new = SLTCreatNode(x);

	if (*pphead == pos)
	{
		p_new->next = *pphead;
		*pphead = p_new;
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		p_new->next = prev->next;
		prev->next = p_new;
	

查找数据

返回的是查找到结点的地址

SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
	assert(phead != NULL);

	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

销毁链表（意外的知识）

在C语言和C++中程序员在堆区开辟的数据需要程序员亲手释放，一个一个开出的节点，只能一个一个释放掉。
这里既可以用一级指针也可以用二级指针，不过有个小小的区别，当你用free释放一个指针的动态内存后需要及时置空，那么在这里，我们的头指针phead在释放完链表后也需要及时置空
但是，

• 如果你传的实参是phead本身，那当SLTDestory执行完后，你需要额外的将phead手动置空
• 如果传的是phead的地址，那么在函数SLTDestory中，释放完链表后，就可以操作*pphead = NULL,其实就等于在函数内部将函数外部的phead置空，出了函数，就不需要手动置空了
• 到这里或许是有些抽象，你可以想一下free函数，它把指针释放后，需要你手动置空，实际上原因就是你传的是指针本身，free函数不能在它的内部将这个指针置空，所以需要你在free执行完手动置空

void SLTDestory(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		SLTNode* nxt = cur->next;
		free(cur);
		cur = nxt;
	}
}
void test()
{
	SLTNode* phead = NULL;
	...
	SLTDestory(phead);
	phead = NULL;//手动置空
}

void SLTDestory(SLTNode** pphead)//用二级指针接收phead的地址
{
	SLTNode* cur = *pphead;
	while(cur != NULL)
	{
		SLTNode* nxt = cur->next;
		free(cur);
		cur = nxt;
	}
	*phead = NULL;//远程操作置空
}
void test()
{
	LSTNode* phead = NULL;
	...
	SLTDestory(&phead);//实参是指针变量phead的地址
}

哨兵位

• 哨兵位也算是一个结点，但哨兵位是不计入链表的长度。
• 哨兵位里不需要存值，最好不要存，有的数据结构书上会将哨兵位存入链表的结点个数，但这里的前提是你创建的链表是存储int型的数据，如果是char呢，那么根据数据在内存中的存储方式不同，char型只能存储8个bit的数据，范围也就是-128~127，如果这个链表结点个数大于127，那么这个哨兵位存的数据就会出错，如果换做是浮点型，那就更离谱了，所以哨兵位最好不要存储数据。

初始化

LSTNode* phead = (LSTNode*)malloc(sizeof(LSTNode));
//phead这个指针变量指向哨兵位

传参

有了哨兵位，再也不用为二级指针苦恼了
每当我们可能对链表的头结点进行插入或者删除（实际是phead指向的结点的地址改变了，phead的内容需要更改，只能通过二级指针的方式远程操控phead）
现在哨兵位出现了，你想对链表的头结点进行操作，想改变头结点的地址，随便改，我phead现在指向是哨兵位，哨兵位的地址是固定不变的，再也不用担心要修改链表的同时还要考虑需不需要修改phead的指向，当哨兵位不改变时，链表怎样的增删改，都只会影响哨兵位的指向,与phead无关

这里用头删演示：

void SLTPopFront(SLTNode* phead)
{
	assert(phead != NULL);
	assert(phead->next != NULL);//当链表为空还要删就报错

	SLTNode* tail = phead->next;
	phead->next = tail->next;
	free(tail);
}

为什么都是用头删，头插演示呢，

• 那是因为这两个操作更改的是第一个结点，节点发生改变，那就要更新指向这个结点的指针，现在的函数实参传的是哨兵位的地址，phead指向的也就是哨兵位，传的是哨兵位的地址那就可以对哨兵位进行更新，而远在函数外的头指针，一直指向的都是固定不变的哨兵位的地址。
• 而前面我们如果更改了第一个结点，那就要更新头指针，想在函数里更改函数外的指针只能传指针的地址，指针的地址就需要二级指针接收。
• 当然，重点讲带头单链表的原因也在于算法题里的链表大部分都是带头链表，避免与哨兵位混淆。哨兵位在某些时刻也会帮忙简化一些判断甚至帮助解题，后续有机会讲算法题会提到的。