【数据结构】保姆级单链表教程（概念、分类与实现）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

目录

🍊前言🍊

🍈一、链表概述🍈

1.链表的概念及结构

2.链表存在的意义

🍓二、链表的分类🍓

🥝三、单链表的实现🥝

1.工程文件

2.接口实现本文重点

①.打印单链表

②.申请新节点

③.单链表尾插

④.单链表头插

⑤.单链表尾删

⑥.单链表头删

⑦.单链表查找

⑧.单链表插入

⑨.单链表删除

⑩.单链表销毁

🍉四、链表实现全部源码🍉

1.SList.h

2.SList.c

3.test.c

🍒总结🍒

🛰️博客主页✈️銮同学的干货分享基地

🛰️欢迎关注👍点赞🙌收藏✍️留言

🛰️系列专栏🎈 数据结构

                       🎈【进阶】C语言学习

                       🎈  C语言学习

🛰️代码仓库🎉数据结构仓库

                       🎉VS2022_C语言仓库

        家人们更新不易你们的👍点赞👍和⭐关注⭐真的对我真重要各位路过的友友麻烦多多点赞关注欢迎你们的私信提问感谢你们的转发

        关注我关注我关注我你们将会看到更多的优质内容

🏡🏡 本文重点 🏡🏡

🚅 链表概念与结构 🚃 链表分类 🚃 单链表实现🚏🚏

🍊前言🍊

        在上节课中我们学习了线性表中的顺序表相关知识掌握了顺序表的相关实现与操作。而在这节课中我将带领各位小伙伴们继续学习线性表中的另一个重要部分即链表的相关知识学习。

🍈一、链表概述🍈

1.链表的概念及结构

        链表linked list是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

2.链表存在的意义

        通过上节课的学习我们对顺序表有了较深层次的认知同时我们发现顺序表在创建和使用时存在着一些明显的问题

  • 当空间不足时顺序表需要进行增容但由于顺序表本质为数组数据在物理上连续存放因此在进行扩容时要付出较大的空间代价。
  • 为避免频繁扩容基本每次都扩容 2 倍当扩容次数增多时就很有可能会造成一定程度的空间浪费。
  • 由于顺序表内数据连续存储我们在向顺序表中位置插入或删除数据时就需要挪动大量的数据效率不高。

        于是人们针对顺序表的这些缺陷设计出了链表这个概念来克服这些不足。

        而链表克服这些缺陷的方法是将每一个节点划分为数据与指针两部分数据部分用于存储数据而指针部分用于指向下一节点。这样做的好处是通过指针指向下一节点于是数据的物理存储就可以不必连续于是无论是在扩容还是在插入与删除数据时都能快速、方便的实现并且不会造成很大的空间浪费。

🍓二、链表的分类🍓

1.单向或双向

2.带头或不带头

3.循环或非循环

注虽然有很多种不同的链表结构但是最常用的链表结构主要是两种无头单向非循环链表与带头双向循环链表

  • 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。
  • 带头双向循环链表结构最复杂一般用在单独存储数据。虽然它结构复杂但在实际使用中使用代码实现后优秀的结构会带来很多优势实现反而更加简单。并且在我们的实际中所使用的链表数据结构一般都是带头双向循环链表。

🥝三、单链表的实现🥝

1.工程文件

        与顺序表的实现方式类似也使用模块化开发格式使用 SList.h 、SList.c 、test.c 三个文件进行代码书写

  • SeqList.h存放函数声明、包含其他头文件、定义宏。
  • SeqList.c书写函数定义书写函数实现。
  • test.c书写程序整体执行逻辑。

        这其中我们的接口实现主要研究的是函数实现文件 SeqList.c 中的内容对 test.c 文件中的内容分不关心。

2.接口实现本文重点

        这里是本文重点中的重点即 SeqList.c 文件中的接口具体实现

①.打印单链表

  • 执行操作前无需进行断言原因是循环条件为空指针则条件不满足并停止循环不会出现死循环。
  • 根据指针循环操作打印数据后使指针指向节点内存放下一节点地址的指针 NEXT。
void SListPrint(SLNode* SLHead)
{
	SLNode* cur = SLHead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

②.申请新节点

  • 在各项操作前需动态申请新节点再对新申请的节点进行操作。
SLNode* BuyListNode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
    if (newnode == NULL)
	{
		perror("newnode:>");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

③.单链表尾插

  • 如果此时头节点为空指针说明此时单链表内没有节点此时只需要将申请来的新节点作为头节点即可。
  • 若头节点不为空则应当首相找到尾节点使尾结点指针指向申请来的新节点后再使新节点指针指向空即可。
void SLPushBack(SLNode** pphead, SLDataType x)
{
	SLNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾结点
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
  • 测试尾插接口功能实现

④.单链表头插

  • 头插实现非常简单首先申请新节点先使新节点的指针指向原来的头节点再使链表头指向新节点即可。
  • 这里不需要考虑空节点的原因是就算链表内没有内容即首节点为空新节点指针指向空也没有问题申请新节点时原本就指向空。
void SLPushFront(SLNode** pphead, SLDataType x)
{
	SLNode* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
  • 测试头插接口功能实现

⑤.单链表尾删

  • 执行操作前需要进行非空判断防止传入空指针。
  • 若链表内只有一个节点则直接释放并置空即可。
  • 若有一个以上节点则当执行下面三个步骤
  1. 首先寻找尾节点找到后将其释放并置空。
  2. 但在释放前必须将倒数第二个节点的指针指向空否则将在指向最后一个被释放的节点时变成野指针。
  3. 单向链表无法回溯于是我们应当定义另一个指针在每次移动尾节点指针前保存当前节点的位置。
void SLPopBack(SLNode** pphead)
{
	//判断链表是否为空
	if (*pphead == NULL)
	{
		return;
	}
	//若只有一个节点直接释放并置空即可
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//若有多个节点则执行多步尾删
	else
	{
		SLNode* tail = *pphead;
		SLNode* prev = NULL;
		//找到尾节点
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}
  • 测试尾删接口功能实现

⑥.单链表头删

  • 执行操作前判断指针非空防止对空指针进行操作。
  • 使链表头指向第二个节点接着将第一个节点释放并置空即可。
void SLPopFront(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}
  • 测试头删接口功能实现

⑦.单链表查找

  • 采用遍历思想依次对每一个节点的数据进行判断符合条件即进行打印不符合条件则继续向后遍历直至指向 NULL并且因此无需进行非空判断。
void SLFind(SLNode* phead, SLDataType x)
{
	SLNode* cur = phead;
	int count = 1;
	while (cur)
	{
		if (cur->data == x)
		{
			printf("第%d个节点%p -> %d\n", count++, cur, x);
		}
			cur = cur->next;
	}
}
  • 测试查找接口功能实现

⑧.单链表插入

        单链表在插入新节点时有两种插入方式一种是在目标节点前方插入另一种是在目标节点后方插入因此需要分别进行实现

Ⅰ、单链表前插

  • 前插有两种情况一种是在首节点处插入此时即相当于头插操作。
  • 另一种是在非首节点前插入此时首先申请新节点接着遍历单链表找到插入位置后使新节点指向目标节点后插入其前方。
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{
	//首先申请新节点
	SLNode* newnod = BuyListNode(x);
	if (*pphead == pos)
	{
		newnod->next = *pphead;
		*pphead = newnod;
	}
	else
	{
		//找到目标节点 pos 的前一个节点
		SLNode* PostPrev = *pphead;
		while (PostPrev->next != pos)
		{
			PostPrev = PostPrev->next;
		}
		//找到后插入新节点
		PostPrev->next = newnod;
		newnod->next = pos;
	}
}
  • 测试前插接口功能实现

Ⅱ、单链表后插

  • 在前插操作时我们需要遍历整个链表来查找插入位置因此效率较为低下于是我们通常使用后插的方式插入新节点。
  • 后插直接申请节点插入目标位置后即可。
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	SLNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
  • 测试后插接口功能实现

⑨.单链表删除

  • 单链表的删除很简单分为两种情况进行处理一种情况是整个链表中只有一个节点则删除节点相当于释放整个数组并置空。
  • 另一种情况是含有一个以上节点此时只需要让目标节点的前一个节点指针指向后一个节点再释放目标节点并置空即可。
void SLErase(SLNode** pphead, SLNode* pos)
{
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
		pos = NULL;
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
  • 测试删除接口功能实现

⑩.单链表销毁

  • 遍历整个单链表将每一个节点都进行释放并置空即可。
void SListDestory(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

🍉四、链表实现全部源码🍉

1.SList.h

#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>

typedef int SLDataType;

//单链表节点结构
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SLNode;

void SLPrint(SLNode* SLHead);    //打印单链表
SLNode* BuyListNode(SLDataType x);    //申请新节点
void SLPushBack(SLNode** pphead, SLDataType x);    //单链表尾插
void SLPushFront(SLNode** pphead, SLDataType x);    //单链表头插
void SLPopBack(SLNode** pphead);    //单链表尾删
void SLPopFront(SLNode** pphead);    //单链表头删
void SLFind(SLNode* phead, SLDataType x);    //单链表查找
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x);    //单链表前插
void SLInsertAfter(SLNode* pos, SLDataType x);    //单链表后插
void SLErase(SLNode** pphead, SLNode* pos);    //单链表删除
void SLDestory(SLNode** pphead);    //单链表销毁

2.SList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

//打印单链表
void SLPrint(SLNode* SLHead)
{
	SLNode* cur = SLHead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//申请节点
SLNode* BuyListNode(SLDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("newnode:>");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//单链表尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
	SLNode* newnode = BuyListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾结点
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//单链表头插
void SLPushFront(SLNode** pphead, SLDataType x)
{
	SLNode* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//单链表尾删
void SLPopBack(SLNode** pphead)
{
	//判断链表是否为空
	if (*pphead == NULL)
	{
		return;
	}
	//若只有一个节点直接释放并置空即可
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//若有多个节点则执行多步尾删
	else
	{
		SLNode* tail = *pphead;
		SLNode* prev = NULL;
		//找到尾节点
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

//单链表头删
void SLPopFront(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

//单链表查找
void SLFind(SLNode* phead, SLDataType x)
{
	SLNode* cur = phead;
	int count = 1;
	while (cur)
	{
		if (cur->data == x)
		{
			printf("第%d个节点%p -> %d\n", count++, cur, x);
		}
			cur = cur->next;
	}
}

//单链表前插
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{
	//首先申请新节点
	SLNode* newnod = BuyListNode(x);
	if (*pphead == pos)
	{
		newnod->next = *pphead;
		*pphead = newnod;
	}
	else
	{
		//找到目标节点 pos 的前一个节点
		SLNode* PostPrev = *pphead;
		while (PostPrev->next != pos)
		{
			PostPrev = PostPrev->next;
		}
		//找到后插入新节点
		PostPrev->next = newnod;
		newnod->next = pos;
	}
}

//单链表后插
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	SLNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//单链表删除
void SLErase(SLNode** pphead, SLNode* pos)
{
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
		pos = NULL;
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//单链表销毁
void SLDestory(SLNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

void TestSList1()
{
    SLNode* plist = NULL;
    //单链表尾插
    SLPushBack(&plist, 1);
    SLPushBack(&plist, 2);
    SLPushBack(&plist, 3);
    SLPushBack(&plist, 4);
    SLPrint(plist);
    //单链表后插
    SLInsertAfter(plist->next, 5);
    SLPrint(plist);
}

int main()
{
    TestSList1();
    return 0;
}

//单链表头插
//SLNode* plist = NULL;
单链表尾插
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表头插
//SLPushFront(&plist, 2);
//SLPushFront(&plist, 3);
//SLPushFront(&plist, 4);
//SLPrint(plist);

//单链表尾删
//SLNode* plist = NULL;
单链表尾插
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表尾删
//SLPopBack(&plist);
//SLPopBack(&plist);
//SLPopBack(&plist);
//SLPrint(plist);

//单链表头删
//SLNode* plist = NULL;
单链表尾插
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表头删
//SLPopFront(&plist);
//SLPrint(plist);
//SLPopFront(&plist);
//SLPrint(plist);
//SLPopFront(&plist);
//SLPrint(plist);
//SLPopFront(&plist);
//SLPrint(plist);

//单链表查找
//SLNode* plist = NULL;
单链表尾插
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 4);
//SLPushBack(&plist, 2);
//
//SLPrint(plist);
单链表查找
//SLFind(plist, 2);
//SLPrint(plist);

//单链表前插
//SLNode* plist = NULL;
单链表尾插
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表前插
//SLInsertFront(&plist, (plist->next)->next, 3);;
//SLPrint(plist);

//单链表后插

//单链表删除
//SLNode* plist = NULL;
单链表尾插
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表删除
//SLErase(&plist, (plist->next)->next);
//SLPrint(plist);

//单链表销毁
//SLNode* plist = NULL;
单链表尾插
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表销毁
//SLDestory(plist);
//SLPrint(plist);

🍒总结🍒

        今天我们认识并学习了单向无头链表的相关概念、结构与接口实现并且针对每个常用的功能接口都进行了实现分解并对各个接口的各项注意点都进行了强调说明希望能对各位小伙伴们的链表学习提供一些谨小的帮助。

        🔥🔥努力的时间还不够哪有时间去绝望🔥🔥

        更新不易辛苦各位小伙伴们动动小手👍三连走一走💕💕 ~ ~ ~  你们真的对我很重要最后本文仍有许多不足之处欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：【进阶C语言】通讯录（后期会升级）

下一篇：pytorch入门

“【数据结构】保姆级单链表教程（概念、分类与实现）” 的相关文章

R语言、04 案例P143 Go bananas、《商务与经济统计》案例题1年前 (2023-02-02)
数据价值深度挖掘，分析服务上线“探索”能力1年前 (2023-02-02)
《一个程序猿的生命周期》-《发展篇》- 43.从技术向市场转型的感悟。注：对2022年的结束。1年前 (2023-02-02)
Loj 507 接竹竿 题解1年前 (2023-02-02)
【数据结构】—带头双向循环链表的实现（完美链表）1年前 (2023-02-02)
【前沿技术RPA】 一文了解UiPath 文件与文件夹自动化功能_uipath 获取下载的文件1年前 (2023-02-02)
windows2003 DHCP服务器配置1年前 (2023-02-02)
上古神兵,先天至宝,Win11平台安装和配置NeoVim0.8.2编辑器搭建Python3开发环境(2023最新攻略)1年前 (2023-02-02)
Asp.Net7 与 Vue3 组成的 BFF模式1年前 (2023-02-02)
FPGA实现的SPI协议（一）----SPI驱动_fpga spi1年前 (2023-02-02)

阿里云国际版