什么是链表,如何实现?(单链表篇)

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

欢迎来到 Claffic 的博客 💞💞💞

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

      “仅仅活着是不够的,还需要有阳光,自由和花的芬芳。”

前言:

在日常使用的网站和软件中,列表属于最常见的一种东西了,其实现形式有顺序表,链表等,主要功能有增删查改,那么链表具体是什么,如何实现?这篇博客为你解答。

注:

这篇博客属于数据结构内容,建议学习完C语言的小伙伴食用~


目录

🥰Part1: 何为链表

1.链表的概念

2.链表的结构 

💗Part2: 链表的实现

1.开工准备 

1.1创建项目

1.2建立结点

1.3动态申请结点

2.相关功能实现

2.1打印链表

2.2尾部插入

2.3头部插入

2.4尾部删除

2.5头部删除

2.6查找位置

2.7在pos位置之后插入

2.8删除pos之后的值

2.9pos之前插入

2.10删除pos结点


Part1: 何为链表

1.链表的概念

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

简单理解下这个概念,就是一个存储单元中有 存储的数据 下一个存储单元的地址 ,经过这个存储单元可利用地址找到下一个存储单元。

下面讲到结构就会更加明白: 

2.链表的结构 

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

一个简单链表的逻辑图 

注意:

• 链式结构在逻辑上连续,在物理上不一定连续(存储的地址不连续);

• 现实中的结点一般是从上申请出来的;

• 从堆上申请的空间,按照一定策略分配,两次申请的空间不一定连续。 

Part2: 链表的实现

1.开工准备 

1.1创建项目

按照惯例,在 Single linked list 解决方案中创建三个项:

SList.h:头文件,声明所有函数;

SList.c:源文件,实现各函数;

test.c:  源文件,主函数所在项,可调用各函数。

1.2建立结点

这里创建一个结点的结构体,包含要储存的数据和下一个结点的地址:

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;//指向结构体的指针,可通过它找到下一个结构体
}SLTNode;//将此结点简易命名,方便引用

1.3动态申请结点

关于为什么要动态申请:

动态申请按需分配内存,既不会空间多余,也不会浪费

SLTNode* BuySListNode(SLTDateType x)
{
	//动态申请
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return;
	}

	//初始化
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

注意动态申请后要进行判断和初始化。

2.相关功能实现

2.1打印链表

我们打印的是一个结点中的数据

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;//地址不一定连续,不可++;
	}
	printf("NULL\n");
}

这里值得注意的是 遍历过程中是如何前进的:
 

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

因为地址不一定连续,所以要进行赋值,不可直接++,这一点很重要 

2.2尾部插入

尾部插入,在申请一个新的结点后,要做的最重要的一点就是 末端节点 中的 结构体指针 要指向   新的结点 

尾部插入有两种情况:

• phead 为NULL;

• phead 不为NULL。

我们一个个分析:

第一种情况 比较简单,phead 为空

要让 phead 指向 newnode 指向的结点 ,直接赋值即可

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

*pphead = newnode;//pphead 是指向 phead 的指针,后面会讲利用二级指针的原因

第二种情况 就比较复杂,

因为要实现上下的链接

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

再寻找一个 tail 用来遍历整个链表,遇到 NULL 时停止。

void SListPushBack(SLTNode** pphead, SLTDateType 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;//改变的是结构体成员,用结构体的指针当然可以
	}
}

需要注意的是

形参的改变不影响实参,需要通过二级指针来改变 phead.

如要改变 int* ,就需要通过 int** 来改变。

2.3头部插入

头部插入,包括前后两个方向的链接:一是 phead 要指向新的结点 ,二是 新结点中的结构体指针 指向原链表的第一个结点 

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

我是图示 

void SListPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
    SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.4尾部删除

我的思路是找到倒数第二个结点,但还有只有一个结点的情况。

只有一个结点时,不用查找,直接释放并置空该节点;

有多个结点时,先找到倒数第二个结点,将该节点的下一个结点释放并置空即可。

void SListPopBack(SLTNode** pphead)
{
	
	assert(pphead);
    if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

2.5头部删除

要头部删除,令 phead 指向第二个结点后释放第一个结点即可。

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

2.6查找位置

查找特定数值所在的位置,思路是通过头指针遍历,最多遍历一遍链表

SLTNode* SListFind(SLTNode* plist, SLTDataType x)
{
	SLTNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return cur;
}

最后返回的是 结构体指针 ,也就是数值所在结构体的地址。 

2.7在pos位置之后插入

 在创建 newnode 之后,改变指针指向即可

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

我是图示  

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

注意:要先改变 newnode.next 的值,再改变 pos.next 的值,否则会被覆盖。

2.8删除pos之后的值

可以先找到要删除的结点,也就是pos的下一个结点,再将该节点释放置空 

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

我是图示  

void SListEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos = del->next;
	free(del);
	del = NULL;
}

2.9pos之前插入

如果pos指向第一个结点,就相当于前插

其他情况下,需要找到pos的前一个,再进行修改。 

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

我是图示  

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	
	else
	{
		//查找pos前一个
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.10删除pos结点

寻找pos的前一个,修改其指向,pos释放置空即可

链表实现,小项目,数据结构与算法,链表,数据结构,c语言

我是图示  

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//查找pos前一个
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

 

代码已上传至 我的 gitee

拿走不谢~


总结:

这篇博客介绍了最简单的链表 -- 单链表的概念和结构,并进行了相关功能的实现,第一次接触可能会难很消化,建议充分理解结构后进行实现呐~ 

码文不易 

如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦  💗💗💗文章来源地址https://www.toymoban.com/news/detail-784140.html

到了这里,关于什么是链表,如何实现?(单链表篇)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

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

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

    2023年04月11日
    浏览(121)
  • 【数据结构】认识链表和模拟实现单链表

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

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

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

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

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

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

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

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

    2024年02月14日
    浏览(64)
  • 一起学数据结构(3)——万字解析:链表的概念及单链表的实现

    上篇文章介绍了数据结构的一些基本概念,以及顺序表的概念和实现,本文来介绍链表的概念和单链表的实现,在此之前,首先来回顾以下顺序表的特点: 1. 顺序表是一组地址连续的存储单元依次存储的线性表的数据结构,逻辑上:顺序表中相邻的数据元素,其物理次序也是

    2024年02月13日
    浏览(52)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(54)
  • 数据结构-链表-单链表(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日
    浏览(99)
  • 【数据结构】- 链表之单链表(下)

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

    2023年04月23日
    浏览(60)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包