单链表的介绍和基本操作（C语言实现）【保姆级别详细教学】_Yu_Cblog的博客

单链表的基本操作【超详细备注和解释】
先赞后看好习惯 打字不容易，这都是很用心做的，希望得到支持你 大家的点赞和支持对于我来说是一种非常重要的动力 看完之后别忘记关注我哦！️️️

强烈建议本篇收藏后再食用

单链表基本介绍

对于数据结构这个模块，我们必须要对C语言中的结构体和指针这两部分的内容有很好的掌握，并且要可以灵活地运用。

基本结构

链表：链表是一种在物理储存上非连续，非顺序的储存结构。
链表，顾名思义：就是数据像链条一样串联在一起。
单链表：即单向的链表，即链表是有方向的。
而本篇所要介绍的，是有头有尾的单链表。

以上就是单链表的基本结构，由图我们可以知道，在一个结构里面，我们需要一部分来储存数据，一部分来储存下一个结构体的地址。也就是说，一个结构被划分为数据域和指针域。
在数据结构这一部分内容中，我们习惯将这样的一个结构体称为结点。
同时：我们需要注意的是：在计算机的内存当中，我们的结点并不是像图里那样按照顺序排好的，有可能第一个结点的地址高低一点，第二个低一点，第三个又高一点，但是，这些我们都不关心，因为我们每个结点都有指向下一个结点的指针，相当于是串联起来了，无论结点放在低地址还是高地址，我们都可以找到。

与顺序表的区别以及学习单链表的必要性

顺序表就好像数组一样，每个数据都是按照顺序排列在一起的。而链表不同，链表在空间上是不一定有序的。
于是乎顺序表就显示出了它的一些不便之处。
比如说：我们要在顺序表中某一个位置插入一个数据，我们就要先把后面数据向后挪动一个位置，才能插入…
虽然单链表也有很多缺点，但是，它是很多复杂数据结构的子结构，比如哈希表下面吊着的就是单链表。
因此，我们学习单链表是非常有意义，而且是必要的。

单链表的实现

实现单链表，我们需要三个文件
SList.h,SList.c,test.c

test.c：测试单链表的功能
SList.h:声明实现单链表的相关函数
SList.c：实现单链表相关函数

结点的定义以及头指针的创建

结点的定义非常的简单，我们就简单点，一个数据，一个指针

//SList.h里
typedef int SListDataType;//将我们要存储的数据重新定义一下
//结点
typedef struct SListNode {
	SListDataType data;//数据域
	struct SListNode* next;//指针域
}SListNode;

并且与此同时，我们要在test.c里面创建一个头指针

void TestSList1() {
	//头指针
	SListNode* pList = NULL;//pList永远指着第一个
	//...
	//下面是各种调试函数的测试
}
int main()
{
	TestSList1();
	return 0;
}

单链表的遍历（打印接口的实现）【重点】

要想实现单链表：学会如何遍历是最最最最核心的。 在顺序表中，或者在数组中，我们想要遍历顺序表或者数组，指针++就可以找到下一个数据，但是在单链表中这样可以吗？
很明显是不行的，在链表里面数据根本就不是连续存放的，我们要通过next指针来找下一个结点

void SListPrint(SListNode* phead) {
	//不用assert
	//因为它完全就是有可能为空的
	SListNode* cur = phead;
	while (cur != NULL) {
		printf("%d-->", cur->data);
		cur = cur->next;//这里的next是下一个节点的地址
		//这里不能够是cur++;因为链表结点地址不连续
		//但是我们的指针域里面存了下一个结点的地址，我们直接
		//cur=cur->next;
	}
	//以前顺序表其实就是数组，我们挨个挨个，用循环就可以打印了
	//但是这里不一样，这里是链表，串起来的
	//地址不一定连续
	printf("NULL\n");//这样可以美化一下
}

在这里伙伴们一定要好好地理解cur=cur->next;的含义，这是遍历链表的核心所在。
另外：需要注意的是，SListPrint()这个接口只需要传一级指针就可以了，因为我们只是打印而已，不需要对修改头指针。
这是非常基础的C语言知识了：改谁，就传谁的地址，要传址调用。下面尾插尾删头插头删函数都是可能要修改头指针的，所以我们到时候要穿头指针的地址，也就是一个二级指针。

养成养好习惯，写完一个立马测试，但是现在是个空链表，啥都没有，没得打印，所以我们赶紧把后面的函数写了，顺便再来测试打印函数。
其实理解了链表的遍历原理，细心地写一般来说是不会写bug的。

开辟结点接口

考虑到后面我们要实现各种功能的时候，都有可能要开辟新结点，所以我们直接写一个开辟节点的函数。

SListNode* BuySListNode(SListDataType x) {
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));//开一个结点
	if (newNode == NULL) {
		printf("申请结点失败\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;//一开始我们先把新结点的next置空
	                     //但如果是中间插入或者头插的话，在接口外头我们还要把这个next指向后面的结点
	return newNode;
}

尾插接口

尾插：在链表末尾插入数据

在这里我们要好好分析了
尾插的时候有三种情况：1.原来链表为空链表 2.原来的链表已经有数据了
刚开始学的小伙伴写尾插的时候，其实都比较难想到要分情况。如果不分这两种情况，会发生什么呢？
我们开始：想在最后插入位置插入数据，也就是先创建一个结点，让原本最后一个结点的next指向新结点newNode,怎么找到最后一个结点？
创建指针tail，如果tail->next=NULL;的时候不就是最后一个结点了吗，那有些小伙伴就开始写了–循环while (tail->next != NULL) {}找尾。
如果这样写，我们测试的时候会发现，程序根本跑不过去，为什么？
我们仔细想想，当链表是空链表的时候存在tail->next这玩意儿吗？->是什么操作符？它是一种解引用啊兄弟们，没东西怎么解引用，这不就变成非法解引用了吗，所以，我们要分情况。
即使我们第一次写没有想到，但是这个是我们通过调试代码可以修改出来的。

void SListPushBack(SListNode** pphead, SListDataType x) {
	//这里怎么尾插
	//我们要和顺序表区分开来
	//我们是直接把data插进去吗，插到哪里去，有空间插吗
	//链表的特点是按需索取
	//我们是要先开辟一个空间，放好data，把它放到最后一个结点的后面
	//无论链表为空还是不为空，一上来都要创建一个结点
	SListNode* newNode = BuySListNode(x);

	if (*pphead == NULL) {
		//这种情况，我们要先开一个结点
		//所以我们开结点的过程直接定义成一个接口
		*pphead = newNode;
	}
	else {
		//找尾---遍历
		SListNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;//不为空继续往下走
		}
		//对于链表而言
		//不需要扩容这些东西
		//按需索取
		//对于申请内存来说，顺序表比链表好
		tail->next = newNode;//把新结点地址给tail->next即可
	}
}

有伙伴问，类似tail这些指针不用free()吗，不用，这些只是临时的指针变量，只是帮助我们找尾的而已，结构走完程序自动free()掉他们了，不用我们操心。

写完–测试一下吧

void TestSList1() {
	//头指针
	SListNode* pList = NULL;//pList永远指着第一个
	//...
	//下面是各种调试函数的测试
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPushBack(&pList, 5);
	SListPushBack(&pList, 6);
	SListPrint(pList);
}
int main()
{
	TestSList1();
	return 0;
}

尾删接口

尾删：删除最后面的结点

在这里就不做作解释：思路非常简单，也是要分情况，注意第三种情况：一个以上，我们还需要一个指针prev来记录前一个结点位置

void SListPopBack(SListNode** pphead) {
	//1.空
	//2.一个
	//3.一个以上
	//1.
	if (*pphead == NULL) {
		return;
	}
	//2.
	else if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;//记得置空
	}
	//3.
	else {
		//关键：把前一个的next置空
		SListNode* tail = *pphead;
		//prev:前一个结点
		SListNode* prev = NULL;
		while (tail->next != NULL) {
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;//不要忘记将前一个结点的next置空
	}
}

在这里就不展示测试了，但是希望伙伴们写的时候要记得去测试一下，一分钟的事情。

头插接口

头插：在链表头插入一个结点
单链表的头插就比顺序表要简单很多了，不用挪动数据，思路也非常的简单，这里也不多做解释

void SListPushFront(SListNode** pphead, SListDataType x) {
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;//记得更改头指针的位置
}

头删接口

头删：删除链表头的结点
同样：要分情况讨论
这里还需要一个临时记录位置的结点，防止我们更改头指针的时候找不到前面的结点了。

void SListPopFront(SListNode** pphead) {
	//1.空
	//2.一个结点
	//3.一个以上的结点
	if (*pphead == NULL) {
		return;
	}
	else {
		//怎么删呢？
		//1.先free掉第一个-->不行：找不到下一个了
		//2.先让pList指向下一个--->不行：找不到我们要free的那个了
		//正确的做法：先让一个临时指针充当next的作用，free掉，再让pList指向临时next的位置
		//或者用临时指针保存我们要free的，pList先走也可以

		//此时我们发现，我们这个代码也可以处理只有一个结点的情况，所以第二种第三种情况合并
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

查找接口

查找结点这个接口同时也可以完成改动结点数据的任务，因为该接口可以返回一个结点的地址。

SListNode* SListFind(SListNode* phead, SListDataType x) {
	SListNode* cur = phead;
	while (cur != NULL) {//遍历过程
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;//循环走完找不到，返回空指针
}

我们测试的时候顺便改一下

//test.c里
	SListNode* pos = SListFind(pList, 3);
	if (pos) {//如果查找接口返回的不是NULL，则修改
		pos->data = 30;//找到了我们自然就可以修改了
	}
	SListPrint(pList);

测试一下

void TestSList1() {
	//头指针
	SListNode* pList = NULL;//pList永远指着第一个
	//...
	//下面是各种调试函数的测试
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPushBack(&pList, 5);
	SListPushBack(&pList, 6);
	SListPrint(pList);
	SListNode* pos = SListFind(pList, 3);
	if (pos) {//如果查找接口返回的不是NULL，则修改
		pos->data = 30;
	}
	SListPrint(pList);
}
int main()
{
	TestSList1();
	return 0;
}

在pos位置后插入结点

思路也非常的简单，这里也不多做解释，代码也很容易明白

void SListInsertAfter(SListNode* pos, SListDataType x) {
	assert(pos);//这里是要断言的,因为给的pos不能为空
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;//先把后面的地址给新结点，再将前一个的next改成新结点地址
	pos->next = newnode;
}

删除pos位置后的结点

注意：此处最好定义临时指针，防止丢失内存

void SListEraseAfter(SListNode* pos) {
	assert(pos);
	if (pos->next) {
		//pos->next=pos->next->next;
		//不推荐这种写法，这样一些我们原来的pos->next就不见了
		SListNode* next = pos->next;
		SListNode* next_next = next->next;
		pos->next = next_next;
		free(next);
	}
}

思考

写到这里，我们单链表的基本操作的各种接口已经实现完成了。
我们要思考一个问题，为什么最后两个接口是要操作pos位置后的结点，而不是pos，而不是pos之前的？
插在当前位置可以吗，插在前面可以吗？
都可以，但是为什么不好？
我们在前面插入，在当前位置插入，需要的是前面的前面的next，或者前面的next
怎么获得？遍历单链表，所以我们还得传头指针过去。
如果我们pos恰好是第一个位置，变成头插了，改变头指针位置，我们就还得传pphead
所以，最好的接口，就是插在后面，这也是单链表的缺陷
如果想要想在哪修改就在哪修改—>用双链表就可以了

测试代码和头文件代码完整展示

test.c

void TestSList1() {
	//头指针
	SListNode* pList = NULL;//pList永远指着第一个
	//...
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPushBack(&pList, 5);
	SListPushBack(&pList, 6);
	//这里要传地址，所以SList.c那边要用二级指针来接受
	SListPrint(pList);
	//打印是不需要传地址的，因为不需要改变内容，跟以前C语言学的是一样的道理

	SListPopBack(&pList);
	SListPopBack(&pList);
	SListPrint(pList);


	SListPushFront(&pList, 0);
	SListPushFront(&pList, -1);
	SListPushFront(&pList, -2);
	SListPrint(pList);

	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPopFront(&pList);
	SListPrint(pList);
}
void TestSList2() {
	//头指针
	SListNode* pList = NULL;//pList永远指着第一个
	//...
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPushBack(&pList, 5);
	SListPushBack(&pList, 6);
	SListPrint(pList);
	//测试查找，顺便修改一下
	SListNode* pos = SListFind(pList, 3);
	if (pos) {//如果查找接口返回的不是NULL，则修改
		pos->data = 30;
	}
	SListPrint(pList);
}
int main() {
	TestSList1();
	TestSList2();
	return 0;
}

SList.h

#pragma once

#include<stdio.h>
#include<assert.h>
typedef int SListDataType;
//结点
typedef struct SListNode {
	SListDataType data;//数据域
	struct SListNode* next;//指针域
}SListNode;

//尾插
void SListPushBack(SListNode** pphead, SListDataType x);
//尾删
void SListPopBack(SListNode** pphead);
//头插
void SListPushFront(SListNode** pphead, SListDataType x);
//头删
void SListPopFront(SListNode** pphead);
//查找
SListNode* SListFind(SListNode*phead, SListDataType x);
//pos位置后插入
void SListInsertAfter(SListNode*pos, SListDataType x);
//删除pos位置后的值
void SListEraseAfter(SListNode* pos);
//打印
void SListPrint(SListNode* phead);

尾声

看到这里，相信伙伴们已经对单链表已经有了基本了解，掌握了基本的操作接口实现方法。其实单链表在以后的学习工作中，并不是特别的实用，因为单链表也有很多缺陷。但是，掌握单链表是我们以后学习复杂数据结构的必须要的。
如果看到这里的你感觉这篇博客对你有帮助，不要忘了收藏，点赞，转发，关注哦。