探索数据结构：单链表的实战指南


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty‘s blog

前言

在上一章节中我们讲解了数据结构中的顺序表，知道了顺序表的空间是连续存储的，这与数组非常类似，为我们随机访问数据提供了便利的条件。但是同时当插入数据时可能存在移动数据与扩容的情况，这大大增加我们的时间与空间成本。为了解决这个问题，就要学习我们今天要讲解的链表。

1. 什么是链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。与顺序表不同，链表的存储数据在内存是随机分布的。

2. 链表的分类

链表的种类多种多样，其中最常见的有八种，它们大致可以分为三类：

2.1 单向或者双向

2.2 带不带头节点

2.3 循环不循环

本专栏将选择其中两种常见链表进行讲解，那就是无头单向非循环链表与与带头双向循环链表，这两种优点主要有：

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3. 单链表的功能

单链表的主要功能有以下几个：

  1. 打印单链表中的数据。
  2. 对单链表进行头插(开头插入数据)。
  3. 对单链表进行头删(开头删除数据)。
  4. 对单链表进行尾插(末尾插入数据)。
  5. 对单链表进行尾删(末尾删除数据)。
  6. 对单链表进行查找数据。
  7. 对单链表数据进行修改。
  8. 任意位置的删除和插入数据。
  9. 销毁单链表。

4. 单链表的定义

单链表的结点定义方式与我们以往定义的方式都不同，它是一个结构体中包含两个成员。一个是存储数值，一个存放下一个结点的地址。

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;

实际内存存储结构：

5. 单链表功能实现

5.1 打印单链表

打印链表需要对函数传参指向链表的指针，首先为了保证链表不为空(NULL)，需要对其进行断言。

(1) 代码实现
void PrintSList(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
(2) 复杂度分析
  • 时间复杂度：因为需要遍历整个链表，显然时间复杂度为O(N)。
  • 空间复杂度：打印链表不需要格外的空间，所以空间复杂度为O(1).

5.2 单链表头插

(1) 创建结点

单链表每次插入都需要插入一个节点，所以我们最好写一个创建节点的函数方便后续调用。

SListNode* SListCreatNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
        	return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
(2) 头插代码实现

单链表的头插与顺序表头插最大的不同就是单链表传参需要二级指针。因为头插数据需要改变一级指针plist的指向，而形参的改变无法影响实参，所以需要二级指针才能改变一级指针plist的指向。

void SListPushFront(SListNode** plist, SLTDataType x)
{
	assert(plist);
	SListNode* newnode = SListCreatNode(x);
	newnode->next = *plist;
	*plist = newnode;
}
(3) 复杂度分析
  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

5.3 单链表头删

头删与头插类似，都可能需要改变plist的指向，所以也需要二级指针。并且也需要防止链表为空的情况发生。

(1) 代码实现
void SListPopFront(SListNode** plist)
{
	assert(plist);
	assert(*plist);
	SListNode* cur = (*plist)->next;
	free(*plist);
	*plist = cur;
}
(2) 复杂度分析
  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

5.4 单链表尾插

当链表为空时，单链表尾插就会变成单链表头插，也需要改变plist的指向。其余情况即可通过循环寻找尾节点。

(1) 代码实现
void SListPushBack(SListNode** plist, SLTDataType x )
{
	assert(plist);
	if (*plist== NULL)
	{
		*plist = SListCreatNode(x);
	}
	else
	{
		SListNode* ptail = *plist;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = SListCreatNode(x);
	}
}
(2) 复杂度分析
  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

5.5 单链表尾删

与单链表尾插类似，当链表只有一个头结点时需要将plist置为空，所以也需要二级指针。并且也需要防止链表为空的情况发生。

(1) 代码实现
void SListPopBack(SListNode** plist)
{
	assert(plist);
	assert(*plist);//防止链表为空
	if ((*plist)->next == NULL)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		SListNode* ptail = *plist;
		while (ptail->next->next)
		{
			ptail = ptail->next;
		}
		free(ptail->next);
		ptail->next = NULL;
	}	
}
(2) 复杂度分析
  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

5.6 单链表的查找

如果找到就返回这个节点的地址，否则就返回空指针NULL

(1) 代码实现
SListNode* SListSearch(SListNode* plist, SLTDataType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
(2) 时间复杂度
  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

5.6 单链表的修改

单链表的修改可以与查找配套使用。

(1) 代码实现
void SListModify(SListNode*plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur == pos)
		{
			cur->data = x;
			break;
		}
		cur = cur->next;
	}
}
(2) 复杂度分析
  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

5.7 单链表任意位置的插入

(1) 代码实现

某个位置之前插入，当链表为空或者在头节点插入时使用头插。

void SListInsertF(SListNode** plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	if (*plist == pos || *plist == NULL)
	{
		SListPushFront(plist, x);//头插
	}
	else
	{

		SListNode* newnode = SListCreatNode(x);
		SListNode* prev = *plist;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

某个位置之后插入，当链表为空或者在尾节点插入时使用尾插。

void SListInsertB(SListNode** plist, SListNode* pos, SLTDataType x)
{
	assert(plist);
	assert(pos);
	if (*plist == NULL||pos->next==NULL)
	{
		SListPushBack(plist, x);//尾插
	}
	else
	{
		SListNode* tmp = pos->next;
		SListNode* newnode = SListCreatNode(x);
		pos->next = newnode;
		newnode->next = tmp;
	}
}
(2) 复杂度分析
  • 时间复杂度：无论向前插入还是向后插入都可能需要遍历整个链表，所以时间复杂度为O(N)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

5.8 任意位置的删除

任意位置的删除需要提前保存好前一个节点与后一个节点的位置。

(1) 代码实现
void SListErase(SListNode** plist, SListNode* pos)
{
	assert(plist);
	assert(*plist);
	assert(pos);
	if (*plist == pos)
	{
		SListPopFront(plist);//头删
	}
	SListNode* prev = *plist;
	while (prev->next!=pos)
	{
		prev = prev->next;
	}
	SListNode* tmp = pos->next;
	prev->next = tmp;
	free(pos);
	pos = NULL;
}
(2) 复杂度分析
  • 时间复杂度：可能需要遍历整个链表，所以时间复杂度为O(N)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

5.9 销毁链表

销毁链表需要依次遍历释放节点。

(1) 代码实现
void SListDestroy(SListNode** plist)
{
	assert(plist);
	assert(*plist);
	SListNode* cur = *plist;
	while (cur)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur =tmp;
	}
	*plist = NULL;//防止野指针
}
(2) 复杂度分析
  • 时间复杂度：需要遍历整个链表，所以时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/440850.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Spring知识体系】1.1 Java 注解（Annotation）

【Spring知识体系】1.1 Java 注解（Annotation）

文章目录 1.1 注解（Annotation）1.1.1 什么是注解1.1.2 内置注解1.1.3 元注解（5种）1.14 自定义注解1.15 注解使用场景介绍※ 本文小结 1.1 注解（Annotation） 1.1.1 什么是注解 注解的定义：它提…
阅读更多...
Java中接口新增的方法（默认方法，静态方法，私有方法）

Java中接口新增的方法（默认方法，静态方法，私有方法）

Java中接口新增的方法（默认方法，静态方法，私有方法）
阅读更多...
遗传算法理解与代码实战（二）- demo（python+deap）

遗传算法理解与代码实战（二）- demo（python+deap）

前文介绍了遗传算法，并且手动python代码进行了实践，但是在遇到复杂的问题时（遗传算法理解与代码实战（三）会介绍），手写代码很麻烦，所以需要借助专门的遗传算法库来实现，这…
阅读更多...
使用Python快速提取PPT中的文本内容

使用Python快速提取PPT中的文本内容

直接提取PPT中的文本内容可以方便我们进行进一步处理或分析，也可以直接用于其他文档的编撰。通过使用Python程序，我们可以快速批量提取PPT中的文本内容，从而实现高效的信息收集或对其中的数据进行分析。本文将介绍如何使用Python程序提取Powe…
阅读更多...
Vue | 基于 vue-admin-template 项目的跨域问题解决方法

Vue | 基于 vue-admin-template 项目的跨域问题解决方法

目录 一、现存问题 二、解决方法 2.1 修改的第一个地方 2.2 修改的第二个地方 2.3 修改的第三个地方 自存 一、现存问题 报错截图如下： 二、解决方法 2.1 修改的第一个地方 在 .env.development 文件中： # base api # VUE_APP_BASE_API /d…
阅读更多...
阿里云服务器地域和可用区选择及关系说明

阿里云服务器地域和可用区选择及关系说明

阿里云服务器地域和可用区怎么选择？地域是指云服务器所在物理数据中心的位置，地域选择就近选择，访客距离地域所在城市越近网络延迟越低，速度就越快；可用区是指同一个地域下，网络和电力相互独立的区域&#…
阅读更多...
如何使用Python的Open3D 库LAS对点云进行重建

如何使用Python的Open3D 库LAS对点云进行重建

在 Python 中对点云进行重建也可以使用 PCL 库，不过更为常见的是使用 Open3D 库。Open3D 是一个开源的现代化 3D 数据处理库，提供了许多用于点云和三维几何数据处理的功能，包括点云重建。 下面是一个简单的示例代码，演示了如何使…
阅读更多...
人工智能|机器学习——k-近邻算法(KNN分类算法)

人工智能|机器学习——k-近邻算法(KNN分类算法)

1.简介 k-最近邻算法，也称为 kNN 或 k-NN，是一种非参数、有监督的学习分类器，它使用邻近度对单个数据点的分组进行分类或预测。虽然它可以用于回归问题，但它通常用作分类算法，假设可以在彼此附近找到相似点。 对于分类…
阅读更多...
灵魂指针，教给（二）

灵魂指针，教给（二）

欢迎来到白刘的领域 Miracle_86.-CSDN博客 系列专栏 C语言知识 先赞后看，已成习惯 创作不易，多多支持！ 目录 一、数组名的理解 二、使用指针访问数组 三、一维数组传参本质 四、冒泡排序 五、二级指针 六、指针数组 七、指针数组…
阅读更多...
Go语言物联网开发安科瑞ADW300/4G电能表数据上传mqtt平台-电表接线到传输数据完整流程

Go语言物联网开发安科瑞ADW300/4G电能表数据上传mqtt平台-电表接线到传输数据完整流程

电能表功能说明 ADW300是方便用户进行用电监测、集抄和管理，可灵活安装在配电箱中，可用于电力运维、环保监管等在线监测类平台中。我们本案例是用于工业售电公司对出售电的管理，设备可以监控用电情况、故障监控及警报，售电公司可…
阅读更多...
LeetCode的使用方法

LeetCode的使用方法

LeetCode的使用方法 一、LeetCode是什么？1.LeetCode简介2.LeetCode官网 二、LeetCode的使用方法1.注册账号2.力扣社区力扣编辑器 2.1 讨论发起讨论参与讨论关注讨论 2.2 文章撰写文章关注文章 3.力扣面试官版测评面试招聘竞赛 4.力扣学习LeetBook 书架我的阅读猜您喜…
阅读更多...
使用Opencv库直接进行人脸检测

使用Opencv库直接进行人脸检测

import cv2abs_path cv2.__file__ xml_path abs_path.rsplit("/",1)[0] "/data/haarcascade_frontalface_default.xml"# 加载人脸检测器 face_cascade cv2.CascadeClassifier(xml_path)# 加载图像 img cv2.imread(/media/datasets/face/liuyigei_duo.…
阅读更多...
C++vector的使用方法

C++vector的使用方法

文章目录 一、vector的介绍1. 文档链接2. 简要介绍 二、vector的使用1.vector的定义（1）构造函数（2）拷贝构造函数（2）赋值重载 2. vector 增删查改（1）operator []（2&#x…
阅读更多...
地址分词 | EXCEL批量进行地址分词，标准化为十一级地址

地址分词 | EXCEL批量进行地址分词，标准化为十一级地址

一 需求 物流需要对用户输入地址进行检查，受用户录入习惯地址可能存在多种问题。 地址标准化是基于地址引擎和地址大数据模型，自动将地址信息标准化为省、市、区市县、街镇、小区、楼栋、单元、楼层、房屋、房间等元素，补充层级缺失数据、构建…
阅读更多...
C语言从入门到精通 第十一章（文件操作）

C语言从入门到精通 第十一章（文件操作）

写在前面： 本系列专栏主要介绍C语言的相关知识，思路以下面的参考链接教程为主，大部分笔记也出自该教程。除了参考下面的链接教程以外，笔者还参考了其它的一些C语言教材，笔者认为重要的部分大多都会用粗体标注&#xf…
阅读更多...
【学习笔记】微信运营工具

【学习笔记】微信运营工具

办公工具 在线 http://uzer.meMindMaster即刻（APP）收趣（APP）MindMaster（app） 安装 文字工具 Mega Emoji 文字云 石墨文档 giftools 音频工具 变声实验室（APP） 录音APP&am…
阅读更多...
本鲸多方位助力创业者高效对接创新创业机遇

本鲸多方位助力创业者高效对接创新创业机遇

在科技创新的浪潮中，创业者们不断探索着新的商业机会，寻求着创新创业的道路。然而，面对复杂多变的市场环境和激烈的竞争压力，如何高效对接创新创业机遇成为了摆在创业者面前的重要课题。 本鲸依托海南本鲸投资有限公司和重庆本鲸…
阅读更多...
Flink 物理执行图

Flink 物理执行图

文章目录 物理执行图一、Task二、ResultPartition三、ResultSubpartition四、InputGate五、InputChannel 物理执行图 JobManager根据ExecutionGraph对作业进行调度，并在各个TaskManager上部署任务。这些任务在TaskManager上的实际执行过程就形成了物理执行图。物理…
阅读更多...
Leetcode - 周赛387

Leetcode - 周赛387

目录 一，3069. 将元素分配到两个数组中 I 二，3070. 元素和小于等于 k 的子矩阵的数目 三，3071. 在矩阵上写出字母 Y 所需的最少操作次数 四，3072. 将元素分配到两个数组中 II 一，3069. 将元素分配到两个数组中 I 本…
阅读更多...
[递归、搜索、回溯]----递归

[递归、搜索、回溯]----递归

前言 作者：小蜗牛向前冲 专栏：小蜗牛算法之路 专栏介绍："蜗牛之道，攀登大厂高峰，让我们携手学习算法。在这个专栏中，将涵盖动态规划、贪心算法、回溯等高阶技巧，不定期为你奉上基础数据结构…
阅读更多...
最新文章

Copyright @ 2022~2023