【数据结构】单链表—C语言版（全网最最最最细！小白必必必必看！！！有图有真相！）

文章目录

• 🐸一、前言
• 🐸二、单链表与顺序表的区别
• • 🐵1.存储形式上的区别
  • 🐵2.空间上的区别
  • 🐵3.时间上的区别
• 🐸三、单链表详解
• • 🍎创建单链表
  • ⭕接口1：定义结构体（SLTNode）
  • ⭕接口2：打印（SLTPrint）
  • ⭕接口3：释放（SLTDestroy）
  • ⭕接口4：创建新结点（BuyLTNode）
  • ⭕接口5：头插（SLTPushFront）
  • ⭕接口6：尾插（SLTPushBack）
  • ⭕接口7：头删（SLTPopFront）
  • ⭕接口8：尾删（SLTPopBack）
  • ⭕接口9：查找（SLTFind）
  • ⭕接口10：修改（SLTModify）
  • ⭕接口11：在pos位置之前插入数据（SLTInsert）
  • ⭕接口12：在pos位置之后插入数据（SLTInsertAfter）
  • ⭕接口13：删除pos位置的值（SLTErase）
  • ⭕接口14：删除pos位置之后的值（SLTEraseAfter）
• 🐸四、完整代码
• • 🥝SList.h
  • 🥝SList.c
  • 🥝Test.c

🐸一、前言

终于放假啦！🤩🤩停更了两个月，在假期要把欠下的补回来&有规律的学习！🤓

本篇文章来自《数据结构与算法》 专栏，本篇的内容是单链表的学习，也是数据结构的基础，希望烙铁们可以理解消化哦🥰！！！

🐸二、单链表与顺序表的区别

🐵1.存储形式上的区别

顺序表 在物理上和逻辑上都是连续的

单链表 在物理上是不连续的，在逻辑上是连续的

🐵2.空间上的区别

顺序表一般有固定的空间大小，当空间不够时需要进行扩容，扩容时往往不能准确知道需要扩容的空间大小，很容易会造成空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

单链表 用一个空间申请一个空间，相比顺序表不那么浪费空间（并不是完全不浪费）

总结 ：在存储数据时，如果知道具体空间大小，就用顺序表进行存储，不知道具体空间大小，就用单链表

🐵3.时间上的区别

1️⃣随机插入、删除元素的时间复杂度：

顺序表：时间复杂度为 O(n)，因为其空间是连续的，在某个位置插入时，这个位置后面的元素都要往后挪动位置；

单链表：时间复杂度为 O(1)，只需要改变前驱元素及插入删除元素的指向；

2️⃣查找指定元素，修改指定位置元素的时间复杂度：

顺序表：时间复杂度为 O(1)，依靠下标直接可以找到指定元素，对其操作；

单链表：时间复杂度为 O(n)，需要从链表头结点往下遍历；

🐸三、单链表详解

🍎创建单链表

🥰这里先创建三个文件：

1️⃣：SList.h文件，用于函数的声明

2️⃣：SList.c文件，用于函数的定义

3️⃣：Test.c文件，用于测试函数

建立三个文件的目的： 将单链表作为一个项目来进行编写，方便我们的学习与观察。

⭕接口1：定义结构体（SLTNode）

🥰请看代码与注释👇

//自定义类型
typedef int SLTDataType;

//创建单链表
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

⭕接口2：打印（SLTPrint）

🥰请看代码与注释👇

//打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

⭕接口3：释放（SLTDestroy）

🥰请看代码与注释👇

//释放
void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);

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

⭕接口4：创建新结点（BuyLTNode）

🥰请看代码与注释👇

//创建新结点
SLTNode* BuyLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("mallic fail");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

⭕接口5：头插（SLTPushFront）

🥰请看代码与注释👇

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{ 
	assert(pphead);   //链表为空，pphead也不为空，因为他是头指针plist的地址
	                  // *pphead 不能断言，链表为空，也需要能插入
	SLTNode* newnode = BuyLTNode(x);

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

⭕接口6：尾插（SLTPushBack）

🚨主要思想就是 找尾,要注意尾插有两种情况：空链表和非空链表

很多烙铁容易找错，这里要找的是尾结点，而不是空

尾结点（tail）：next为空的

🥰请看代码与注释👇

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyLTNode(x);

	//1.空链表
	//2.非空链表
	if (*pphead == NULL)
	{
		*pphead = newnode;    //改变的结构体的指针plist（用结构体指针的地址）
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
	                           
		tail->next = newnode;    //改变的结构体尾结点
	}
}

⭕接口7：头删（SLTPopFront）

🚨要注意头删有三种情况：1.没有结点（空链表）、2.一个结点、3.多个结点

链表为空不能头删，所以要进行assert断言

🥰请看代码与注释👇

//头删
void SLTPopFront(SLTNode** pphead)
{
	//没有结点(空链表)
	assert(*pphead);  //链表为空，不能头删
	assert(pphead);
	
	//一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个结点
	else
	{
		SLTNode* cur = *pphead;
		*pphead = cur->next;
		free(cur);
	}
}

可以有更简洁高效的写法👇

🥰请看代码与注释👇

//头删
void SLTPopFront(SLTNode** pphead)
{
	//没有结点(空链表)
	assert(*pphead);
	assert(pphead);

	//一个结点
	//多个结点
	SLTNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}

⭕接口8：尾删（SLTPopBack）

🚨要注意尾删同样有三种情况：1.没有结点（空链表）、2.一个结点、3.多个结点

链表为空不能尾删，所以要进行assert断言

🥰请看代码与注释👇

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//没有结点(空链表)
	assert(*pphead);
	assert(pphead);

	//一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个结点
	else
	{
		SLTNode* tail = *pphead;
		//找尾
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

⭕接口9：查找（SLTFind）

通过遍历进行查找，通常与修改结合联系使用

🥰请看代码与注释👇

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

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

	return NULL;
}

⭕接口10：修改（SLTModify）

🥰请看代码与注释👇

//修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
	assert(phead);
	assert(pos);
	pos->data = x;
}

⭕接口11：在pos位置之前插入数据（SLTInsert）

🥰请看代码与注释👇

//在pos位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);  //防止给的位置为 空

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

		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

⭕接口12：在pos位置之后插入数据（SLTInsertAfter）

🥰请看代码与注释👇

//在pos位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);  //防止给的位置为 空
	
	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

⭕接口13：删除pos位置的值（SLTErase）

🥰请看代码与注释👇

//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);  //防止给的位置为 空

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

		prev->next = pos->next;
		free(pos);
	}
}

⭕接口14：删除pos位置之后的值（SLTEraseAfter）

🥰请看代码与注释👇

//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

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

🐸四、完整代码

🥝SList.h

#pragma once

#include
#include
#include


//自定义类型
typedef int SLTDataType;

//创建单链表
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


//打印
void SLTPrint(SLTNode* phead);
//释放
void SLTDestroy(SLTNode** pphead);
//创建新结点
SLTNode* BuyLTNode(SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头删
void SLTPopFront(SLTNode** pphead);
//尾删
void SLTPopBack(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x);
//在pos位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);

🥝SList.c

#include"SList.h"

//打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//释放
void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);

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

//创建新结点
SLTNode* BuyLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("mallic fail");
		return;
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{ 
	assert(pphead);   //链表为空，pphead也不为空，因为他是头指针plist的地址
	                  // *pphead 不能断言，链表为空，也需要能插入
	SLTNode* newnode = BuyLTNode(x);

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

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuyLTNode(x);

	//1.空链表
	//2.非空链表
	if (*pphead == NULL)
	{
		*pphead = newnode;    //改变的结构体的指针plist（用结构体指针的地址）
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
	                           
		tail->next = newnode;    //改变的结构体尾结点
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	//没有结点(空链表)
	assert(*pphead);  //链表为空，不能头删
	assert(pphead);
	
	//一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个结点
	else
	{
		SLTNode* cur = *pphead;
		*pphead = cur->next;
		free(cur);
	}
}

//头删
//void SLTPopFront(SLTNode** pphead)
//{
//	//没有结点(空链表)
//	assert(*pphead);
//	assert(pphead);
//
//	//一个结点
//	//多个结点
//	SLTNode* cur = *pphead;
//	*pphead = (*pphead)->next;
//	free(cur);
//}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//没有结点(空链表)
	assert(*pphead);
	assert(pphead);

	//一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//多个结点
	else
	{
		SLTNode* tail = *pphead;
		//找尾
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

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

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

	return NULL;
}

//修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
	assert(phead);
	assert(pos);
	pos->data = x;
}

//在pos位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);  //防止给的位置为 空

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

		SLTNode* newnode = BuyLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//在pos位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);  //防止给的位置为 空
	
	SLTNode* newnode = BuyLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);  //防止给的位置为 空

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

		prev->next = pos->next;
		free(pos);
	}
}

//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

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

🥝Test.c

#include"SList.h"

//头插测试
void TestSList01()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);

	SLTPrint(plist);

	SLTDestroy(&plist);
}

//尾插测试
void TestSList02()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);

	SLTPushBack(&plist, 5);
	SLTPushBack(&plist, 6);
	SLTPushBack(&plist, 7);

	SLTPrint(plist);

	SLTDestroy(&plist);
}

//头删测试
void TestSList03()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTDestroy(&plist);
}

//尾删测试
void TestSList04()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTDestroy(&plist);
}

//查找修改测试
void TestSList05()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 3);
	if (pos)
	{
		SLTModify(plist, pos, 8);
	}

	SLTPrint(plist);
	SLTDestroy(&plist);
	
}

//在pos位置之前插入数据测试
void TestSList06()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 3);
	if (pos)
	{
		SLTInsert(&plist, pos, 30);
	}

	SLTPrint(plist);
	SLTDestroy(&plist);
}

//在pos位置之后插入数据测试
void TestSList07()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
	{
		SLTInsertAfter(pos, 20);
	}

	SLTPrint(plist);
	SLTDestroy(&plist);
}


//删除pos位置的值测试
void TestSList08()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 3);
	if (pos)
	{
		SLTErase(&plist,pos);
	}

	SLTPrint(plist);
	SLTDestroy(&plist);
}

//删除pos位置之后的值测试
void TestSList09()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);

	SLTNode* pos = SLTFind(plist, 2);
	if (pos)
	{
		SLTEraseAfter(pos);
	}

	SLTPrint(plist);
	SLTDestroy(&plist);
}

int main()
{
	//TestSList01();
	//TestSList02();
	//TestSList03();
	//TestSList04();
	//TestSList05();
	//TestSList06();
	//TestSList07();
	//TestSList08();
	//TestSList09();

	return 0;
}

😍这期内容些许复杂，需要慢慢理解消化哦！

总结🥰

以上就是 【数据结构】单链表—C语言版 的全部内容啦🥳🥳🥳🥳

本文章所在【数据结构与算法】专栏，感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳

前途很远，也很暗，但是不要怕，不怕的人面前才有路。💕💕💕

小的会继续学习，继续努力带来更好的作品😊😊😊

创作写文不易，还多请各位大佬uu们多多支持哦🥰🥰🥰