数据结构—＞带你深入了解单链表（基础篇）

✅作者简介：大家好，我是橘橙黄又青，一个想要与大家共同进步的男人😉😉

🍎个人主页：橘橙黄又青-CSDN博客

前面我们学习了顺序表，今天我们来学习与顺序表类似的单链表

1.🍎什么是链表

struct SListNode
{
 int data; //节点数据
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};

 2. 🍎链表的打印

那给定的链表结构中，如何实现节点从头到尾的打印？

看图：

代码：

//打印
void SLTPrint(SLTNode* phead) {
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//开辟空间
SLTNode* SLTBuyNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

这样就可以了， 这里补充说明：

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、节点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

 前面简单学习打印，接下来我们进入单链表的增，删，查。

3，🍎单链表的基础应用

 这里我们介绍一下我的单链表代码：

typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

创建一个这样的空间链表： 

3.1🍎链表的尾插

代码展示：

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	SLTNode* newnode = SLTBuyNode(x);

	//链表为空，新节点作为phead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空，找尾节点

    //创建代跑变量
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptail就是尾节点
	ptail->next = newnode;
}

 图片展示：

值得注意的是开辟的空间next是指向nuLL的 

3.2🍎链表的头插

代码展示：

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);

	//newnode *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}

图片展示： 

3.3🍎链表的头删

代码：

void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//让第二个节点成为新的头
	//把旧的头结点释放掉
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

思路：

3.4🍎链表的尾删

代码：

void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//链表不为空
	//链表只有一个节点，有多个节点
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)//找尾节点
	{
		prev = ptail;
		ptail = ptail->next;
	}

	prev->next = NULL;
	//销毁尾结点
	free(ptail);
	ptail = NULL;
}

 把尾节点释放掉，置为空

3.5🍎链表的查找

代码:

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur) //等价于pcur != NULL
	{
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

这个也是很简单，遍历链表，有就返回，无返回空。 

3.6🍎链表在指定位置之前插入数据

代码：

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//要加上链表不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//pos刚好是头结点
	if (pos == *pphead) {
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev -> newnode -> pos
	prev->next = newnode;
	newnode->next = pos;
}

思路：

插入代码就在上面啦。 

3.7🍎链表在指定位置之后插入数据

代码：

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);

	//pos newnode pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}

但是这里要注意了：

思路：

3.8🍎删除pos节点

 代码：

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//pos刚好是头结点，没有前驱节点，执行头删
	if (*pphead == pos) {
		//头删
		SLTPopFront(pphead);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

 思路：

3.9🍎删除pos之后的节点

代码：

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	//pos->next不能为空
	assert(pos->next);

	//pos  pos->next  pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

思路：

3.10🍎销毁链表

堆销毁很重要，创建链表也要学会销毁链表

 代码：

//销毁链表
void SListDesTroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

解释：

创建带跑指针，把下一个节点地址记录下来，释放原来第一个节点空间，再把下一个节点地址给带跑指针。

好啦，我们今天就讲到这里，喜欢就点一个赞吧，感谢观看。