数据结构入门 — 链表详解_单链表

这篇具有很好参考价值的文章主要介绍了数据结构入门 — 链表详解_单链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

数据结构入门 — 单链表详解*
博客主页链接:https://blog.csdn.net/m0_74014525
关注博主,后期持续更新系列文章
文章末尾有源码
*****感谢观看,希望对你有所帮助*****


系列文章

第一篇:数据结构入门 — 链表详解_单链表
第二篇:数据结构入门 — 链表详解_双向链表
第三篇:数据结构入门 — 链表详解_循环链表



一、链表

1. 链表是什么

链表是一种数据结构,由一系列节点组成,在每个节点中存储数据和指向下一个节点的指针。每个节点只包含指向下一个节点的指针,不像数组那样有预定义的大小。链表可以动态地增长和缩小,并且非常灵活,可以在任何位置插入或删除节点。链表主要分为单向链表、双向链表和循环链表等不同类型。

2. 优缺点

链表的优点:

  1. 灵活性:由于链表中每个节点都有指向下一个节点的指针,因此链表可以在任何位置添加或移除元素,使得链表非常灵活。
  2. 动态性:由于链表的大小不是固定的,当需要增加或删除元素时,内存中不需要重新分配空间,而是在链表中增加或删除一个结点。
  3. 无需占用连续的内存空间:相较于数组等数据结构,链表的每个元素之间并没有关联性,每个节点可以在内存中的任意位置,不需要占用连续的内存空间。

链表的缺点:

  1. 没有随机访问的能力:链表中的元素之间没有关联性,无法像数组那样通过下标直接访问某个元素,需要从头开始遍历整个链表才能找到需要的元素,这会导致链表的查找效率比数组低。
  2. 内存空间的额外开销:由于需要在每个节点中存储指向下一个节点的指针,链表内每个元素需要占用比其存储内容更多的内存空间,这会导致链表没有数组那么节省内存。
  3. 不支持常量时间内的随机访问:链表只能在头尾节点进行快速的插入和删除操作,但在其他位置插入和删除节点较为困难,需要先遍历找到要操作的位置,这会导致链表操作的时间复杂度较高。

二、概念及结构

1. 概念

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

2. 结构

在现实的数据结构中,链表的结构
数据结构入门 — 链表详解_单链表,数据结构,数据结构,链表,visual studio,c++,c语言,开发语言
注意:

  1. 从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
  2. 现实中的结点一般都是从堆上申请出来的
  3. 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

三、 链表的分类

1. 链表结构类型

链表可以分为单链表、双向链表和循环链表三种类型。

类型 介绍
单链表 节点只包含一个指向后继节点的指针,每个节点只知道下一个节点的位置。
双向链表 节点包含一个指向前驱节点和一个指向后继节点的指针,每个节点都知道前面和后面的节点位置。
循环链表 链表的最后一个节点指向第一个节点,形成一个环形结构。

除了这三种基本类型,还有一些派生的链表结构,如带有头节点的链表、带有尾指针的链表、带有哨兵节点的链表等。如下图有8种链表结构
1. 单向或者双向
数据结构入门 — 链表详解_单链表,数据结构,数据结构,链表,visual studio,c++,c语言,开发语言

2. 带头或者不带头(哨兵位)
数据结构入门 — 链表详解_单链表,数据结构,数据结构,链表,visual studio,c++,c语言,开发语言

3. 循环或者不循环

数据结构入门 — 链表详解_单链表,数据结构,数据结构,链表,visual studio,c++,c语言,开发语言

2. 常用的两种链表结构

无头单向非循环链表:

数据结构入门 — 链表详解_单链表,数据结构,数据结构,链表,visual studio,c++,c语言,开发语言
无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

带头双向循环链表:
数据结构入门 — 链表详解_单链表,数据结构,数据结构,链表,visual studio,c++,c语言,开发语言
带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都
是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带
来很多优势,实现反而简单了,后面我们代码实现了就知道了。


四、单链表接口实现(代码演示)

无头+单向+非循环链表增删查改实现

1. 动态申请一个结点

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("BuySListNode");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2. 单链表打印

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

3. 单链表增删查改

头插:

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{

	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

尾插:

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{

	assert(pphead);
	SLTNode* newnode = BuySListNode(x);
	
	//如果为空 
	if (*pphead==NULL)
	{
		*pphead = newnode;
	}
	else
	{ 
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

头删:

//头删
void SLTPopFront(SLTNode** pphead)
{

	//空
	assert(pphead);
	assert(*pphead);
	//非空
	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;

}

尾删:

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	assert(pphead);

   //一个节点
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;

	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* tailPrev = NULL;
		while(tail->next != NULL)
		{
			tailPrev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;
		tailPrev->next = NULL;
	}
}

查找:

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

在pos之前插入x:

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{

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

		prev->next = newnode;
		newnode->next = pos;

	}

}

在pos以后插入x:

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
	
}

删除pos位置:

// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(pphead);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除pos的后一个位置:

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

    SLTNode* posNext = pos->next;

	pos->next = posNext->next;

	pos->next = posNext->next;

	free(posNext);

	posNext = NULL;

}

4. 单链表销毁

void Destory(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* del = cur->next;

		free(cur);

		cur = del;
	}

	
	* pphead == NULL;
}

五、所有文件代码

1. Gitee链接

***查看所有代码***
点击右边蓝色文字 DuckBro Gitee 代码仓库


总结

单链表的重点包括:

  1. 定义:单链表是一种数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。
  2. 插入操作:单链表的插入操作需要先找到要插入位置的前一个节点,然后将新节点插入到其后。
  3. 删除操作:单链表的删除操作需要先找到要删除的节点的前一个节点,然后将其指针指向下一个节点即可。
  4. 遍历操作:单链表需要从头节点开始依次遍历各个节点,获取其中存储的数据。
  5. 链表反转:单链表的反转操作是将链表中的节点从后往前连接,最后将原来的头节点变为尾节点。
  6. 快慢指针:快慢指针是单链表中常用的技巧,可以用于查找链表中的中间节点、判断是否有环等操作。
  7. 环形链表:有些单链表可能存在环形结构,即某个节点的指针指向之前的某个节点,使用快慢指针可以判断链表是否为环形。
  8. 链表排序:单链表可以使用排序算法进行排序,如冒泡排序、快速排序等。
  9. 链表的应用:单链表广泛应用于各种数据结构和算法中,如哈希表、图等。

如这篇博客对大家有帮助的话,希望 三连 支持一下 !!! 如果有错误感谢大佬的斧正 如有 其他见解发到评论区,一起学习 一起进步。文章来源地址https://www.toymoban.com/news/detail-679644.html

到了这里,关于数据结构入门 — 链表详解_单链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构-链表-单链表(3)

    目录 1. 顺序表的缺陷 2. 单链表 2.1 单链表的基本结构与接口函数 2.2 重要接口 创建新节点的函数: 2.2.1 尾插 2.2.2 头插 2.2.3 尾删 2.2.4 头删 2.2.5 查找 2.2.6 插入 2.2.7 删除 2.2.8 从pos后面插入 2.2.9 从pos后面删除 3. 链表的缺陷与优势: 4. 链表与顺序表比较 写在最后: 为什么

    2024年01月17日
    浏览(33)
  • 【数据结构】- 链表之单链表(下)

    未来藏在迷雾中 叫人看来胆怯 带你踏足其中 就会云开雾散 本章是关于数据结构中的链表之单链表(下) 提示:以下是本篇文章正文内容,下面案例可供参考 1.2.1 在pos位置插入(也就是pos位置之前) 流程图 多个节点 一个节点 1.2.2 在pos位置之后插入 流程图: 注意: 下面这种写

    2023年04月23日
    浏览(44)
  • <数据结构> 链表 - 单链表(c语言实现)

    哨兵位结点也叫哑节点。哨兵位结点 也是头结点 。该节点 不存储有效数据,只是为了方便操作 (如尾插时用带哨兵位的头结点很爽,不需要判空)。 有哨兵位结点的链表,第一个元素应该是链表第二个节点(head - next,head为哨兵位结点)对应的元素。 有哨兵位结点的链表

    2023年04月11日
    浏览(27)
  • 【数据结构】-- 单链表 vs 双向链表

    🌈 个人主页: 白子寰 🔥 分类专栏: python从入门到精通,魔法指针,进阶C++,C语言,C语言题集,C语言实现游戏 👈 希望得到您的订阅和支持~ 💡 坚持创作博文(平均质量分82+),分享更多关于深度学习、C/C++,python领域的优质内容!(希望得到您的关注~)  目录  单链表和

    2024年04月17日
    浏览(27)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(39)
  • 【数据结构】认识链表和模拟实现单链表

    即使骑的小电驴,也要奋力前进 目录 1.链表 1.1 链表的概念  1.2 链表的逻辑结构图和物理结构图 1.2.1 链表的逻辑结构图  1.2.2 链表的物理结构图  1.3链表结构的分类 1.3.1 链表通过什么进行结构的分类  1.3.2 不同链表结构的逻辑图 2.模拟实现一个单向链表  2.1 MyLinkedList类的

    2024年02月14日
    浏览(30)
  • 【数据结构】 链表简介与单链表的实现

    在【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素 由于其底层是一段连续空间, 当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为

    2024年02月12日
    浏览(36)
  • 【数据结构】链表(单链表与双链表实现+原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月24日
    浏览(38)
  • 【数据结构】--单链表力扣面试题②反转链表

    目录 题目链接:反转链表   法一:直接反转法 法二:头插法 题目分析: 创建一个新链表,然后值是逆置的行吗?不行。因为题目要求的是在 原链表上逆置,改变原链表的指向,并不是值的拷贝后的逆转 。 那其实总共有三种方法 。 法一,直接原地翻转。法二,头插法。

    2024年02月06日
    浏览(27)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

    2024年04月11日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包