数据结构之单链表

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

目录

1.什么是链表。

2.链表的优点

3.单链表的实现

1.单链表的结构体

2.节点的创建

3.参数的调用

4.头插

 5.尾插

7.头删

8.尾删

8.在pos节点前插入x

9.在pos节点前插入x

10.删除pos位置节点 


对于顺序表我们发现,在此基础上仍存在了些许不足:

1.中间或头部的插入时间复杂度为O(n),有点浪费时间。

2.增容需要申请空间,拷贝数据,释放空间,会有不小的消耗。

3.增容一般是呈2倍增容的,势必会造成空间浪费。

如何解决以上问题,我们又了解到了一种新的数据结构-“链表”

1.什么是链表。

链表顾名思义,由一条链子连接表中各成员。实则链表是由每一块独立的空间组成,每一个空间里存放着数据和一个指针,每一个指针指向下一块空间的地址,依次指向,我们可以想象成为用链条串联起类,故叫链表,链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链次序实现的。

数据结构之单链表

就像火车一样数据结构之单链表

我们一般将这一块空间称为一个节点,链表的末尾节点的指针是空指针。

2.链表的优点

相较于顺序表:

1.因为链表是由一块块空间构成,所以链表不存在容量不够要扩容的问题

2.根据需求申请释放空间

3.较好地解决了在头部或中间插入删除挪动数据的问题

3.单链表的实现

这里还是以存放整形数据为例:

1.单链表的结构体

如何来实现这样的结构呢?

数据结构之单链表

typedef int SLdatatype;
typedef struct seqlist
{
	SLdatatype data;
	struct seqlist* next;
}SLnode;

可以看到这里的结构体里存放了本结构体的指针,每一个结构体里都有一个自身的指针,而这个自身的指针就代表下一个结构体的首地址,依次下去,直至到末尾next尾空。

用单链表的话来说,就是每一个节点存放着指向下一个节点地址的指针,故此我们可以创建所需的节点个数存放数据,用指针连接起来。

2.节点的创建

SLnode* SLcreatnode(SLdatatype x)
{
	SLnode* newnode = (SLnode*)malloc(sizeof(SLnode));
	if (newnode == NULL)
	{
		perror("开辟错误\n");
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

每创建一个节点,就是在堆区申请一块空间用来存放数据,利用malloc开辟该结构体大小的空间,之后返回该节点,也就是这片空间。

3.参数的调用

这里强调下参数,因为我们需要改变链表,定义链表变量的时候是指针,函数的参数应设计为二级指针。

对于一个函数我们在其中定义的变量生命周期只在该作用域中,出了作用域就会被销毁,而有的函数需要去改变实参,只是简单的改变形参,是不会影响实参的,但若为实参的地址,我们可通过解引用形参来改变实参,比如:

int swap(int* x, int* y)
{

	int tmp = *x;
	*x = *y;
	*y = tmp;
}
int main()
{
	int x = 10;
	int y = 20;
	swap(&x, &y);
	printf("%d %d", x, y);
	return 0;
}

因此,这里要想通过形参改变实参,参数设计为二级指针:这里以头插为例

数据结构之单链表

4.头插

void SLpushfront(SLnode** p, SLdatatype x)//传参用二级指针
{
	SLnode* newnode = SLcreatnode(x);
	newnode->next = *p;
	*p = newnode;
}

数据结构之单链表

 可以看到头插是先malloc一个节点赋值给newnode,之后在将该newnode 存放到目前的头节点的next中,然后赋值给头节点,即实现头部插入。

 5.尾插

void SLpushback(SLnode** p, SLdatatype x)//尾插
{
	SLnode* newnode = SLcreatnode(x);
	//链表为空的话
	if (*p == NULL)
	{
		*p = newnode;
		(*p)->data = x;
	}
	else
	{
//找尾巴(前提:链表不为空)
	SLnode* tail = *p;
	while (tail ->next!= NULL)
	{
		tail = tail -> next;
	}
	tail->next = newnode;
	(*p)->data = x;
	}
}

尾插需要我们找到最后一个节点,之后先改变末尾的next,(因为保证是连接的)然后再插入。

7.头删

void SLpopfront(SLnode** p)//头删
{
	assert(*p);
	if ((*p) ->next== NULL)
	{
		free(p);
		*p = NULL;
	}
	else
	{
    SLnode* top = *p;
	*p = (*p) -> next;//指向下一个
	free(top);
	top = NULL;
	}
	
}

头删需要分情况

8.尾删

void SLpopback1(SLnode** p)//尾删
{
	SLnode* pre = NULL;
	SLnode* tail = *p;
	while (tail->next != NULL)
	{
	pre = tail;//找到尾节点前一个
	tail = tail->next;
	}
	free(tail);//释放最后的空间
	pre->next = NULL;//同时前一个的next为空
}

或者

void SLpopback2(SLnode** p)
{
	SLnode* tail = *p;
	while(tail->next->next)//找倒数第二个节点
	{
		tail = tail->next;
	}
	free(tail->next);//释放
	tail->next = NULL;//倒数第二个next置空
}

主要找到最后一个节点或者最后一个的前一个节点(这里的两种方法),在释放掉最后一个同时,前一个节点next为NULL。可以看到第二种直接释放掉前一个的next空间,即指向最后一个结点的空间,在置空。

数据结构之单链表

8.在pos节点前插入x

void SLinsert(SLnode** p, SLnode* pos, SLdatatype x)//插在pos位置前
{
	SLnode* newnode = SLcreatnode(x);
	if (pos == *p)
	{
		SLpushfront(p, x);
	}
	SLnode* prev=*p;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
	
}

数据结构之单链表

在这里需要注意在遍历找到pos位置前的一个节点时,我们都是prev->next==pos这样去寻找,但忽略了当头节点就是pos位置时的节点,故在开始我们还需要判断是否头节点等于pos节点,如何果实就直接调用头插

9.在pos节点前插入x

//pos节点后插
void SLinsertafter(SLnode** p, SLnode* pos, SLdatatype x)
{
	
	SLnode* newnode = SLcreatnode(x);
	SLnode* prev = pos->next;
	pos->next = newnode;
	newnode->next = prev;
}

10.删除pos位置节点 

void SLerase(SLnode** p, SLnode* pos)//删除pos位置的节点
{
	SLnode* prev = *p;
	if (*p == pos)
	{
		SLpopfront(p);
		
	}
	else
	{
      while (prev->next != pos)
	   {
		prev = prev->next;
	   }
	prev->next = pos->next;
	free(pos);
	}
	

}

数据结构之单链表文章来源地址https://www.toymoban.com/news/detail-454597.html

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

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

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

相关文章

  • <数据结构> 链表 - 单链表(c语言实现)

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

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

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

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

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

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

    即使骑的小电驴,也要奋力前进 目录 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日
    浏览(58)
  • 【数据结构】链表(单链表与双链表实现+原理+源码)

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

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

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

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

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

    2024年04月11日
    浏览(76)
  • 【数据结构】移除链表元素-图文解析(单链表OJ题)

    LeetCode链接:203. 移除链表元素 - 力扣(LeetCode) 本文导航 💭做题思路 🎨画图更好理解: ✍️代码实现 🗂️分情况讨论: ❄️极端情况: 遍历链表,找到值为 val 的节点删除 这里需要两个指针  cur 用来遍历链表  prev 指向 cur 的前一个位置,方便删除一个节点后,链接前

    2024年02月14日
    浏览(35)
  • 链表的总体涵盖以及无哨兵位单链表实现——【数据结构】

     😊W…Y:个人主页 在学习之前看一下美丽的夕阳,也是很不错的。 如果觉得博主的美景不错,博客也不错的话,关注一下博主吧💕 在上一期中,我们说完了顺序表,并且提出顺序表中的问题 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,拷贝数据,释

    2024年02月14日
    浏览(68)
  • 『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表(单链表&&双向循环链表)附完整源码

      本章内容 1.什么是链表 2.链表常见几种形式 3.无头单向非循环链表的实现 3.1结点结构的定义 3.2函数接口的实现 3.2.1尾插 3.2.2尾删 4. 带头双向循环链表的实现 4.1结点结构的定义 4.2函数接口的实现 5.两种链表的差异 ①尾插与尾删的时间复杂度 ②头插与头删的时间复杂度 ③

    2024年02月16日
    浏览(82)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包