数据结构之单链表及其实现！

目录

​编辑

1.  顺序表的问题及思考

2.链表的概念结构和分类

2.1 概念及结构

2.2 分类

3. 单链表的实现

3.1 新节点的创建

3.2 打印单链表

3.3 头插

3.4 头删

3.5 尾插

3.6 尾删

3.7 查找元素X

3.8 在pos位置修改

3.9 在任意位置之前插入

3.10 在任意位置删除

3.11 单链表的销毁

4. 完整代码

5. 完结散花

                                            悟已往之不谏，知来者犹可追  

创作不易，宝子们！如果这篇文章对你们有帮助的话，别忘了给个免费的赞哟

1.  顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

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

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

2.链表的概念结构和分类

2.1 概念及结构

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

2.2 分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单项或者双向

 2. 带头或者不带头

 3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

下面我就来实现一下无头单向非循环链表~

3. 单链表的实现

这里我就具体实现一下接口~（SList.h)

#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件被多次引用
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SListDataType;//便于改变数据类型

//定义一个结构体类型的节点
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;//存储下一个节点的地址
}SListNode;

//1. 新节点的创建
SListNode* SListCreatNode(SListDataType x);

//2. 打印单链表
void PrintSList(SListNode* phead);

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x);

//4. 头删
void  SListPopFront(SListNode** phead);

//5. 尾差
void SListPushBack(SListNode** phead, SListDataType x);

//6. 尾删
void  SListPopBack(SListNode** phead);

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x);

//8. 在pos位置修改
void SListModify(SListNode* pos, SListDataType x);

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x);

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos);

//11. 销毁单链表
void SListDestroy(SListNode** phead);

3.1 新节点的创建

(1)代码实现

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
	SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	return NewNode;
}

3.2 打印单链表

(1)代码实现

//2. 打印单链表
void PrintSList(SListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL");//如果链表没有元素就打印NULL
		return;
	}
	SListNode* cur = phead;
	//循环单链表打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

(2) 复杂度分析

  • 时间复杂度：因为需要遍历整个链表，显然时间复杂度为O(N)。
  • 空间复杂度：打印链表不需要格外的空间，所以空间复杂度为O(1).

3.3 头插

(1)代码实现

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
	assert(phead);
	SListNode* newnode =SListCreatNode(x);//创建一个新节点
	newnode->next =*phead;
	*phead = newnode;
}

(2) 复杂度分析

  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.4 头删

(1)代码实现

//4. 头删
void  SListPopFront(SListNode** phead)
{
	assert(phead);
	assert(*phead);//如果没有数据就不用头删，并报错
	SListNode* cur = (*phead)->next;
	free(*phead);
	*phead = cur;
}

(2) 复杂度分析

  • 时间复杂度：不需要额外时间的消耗，时间复杂度为O(1)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.5 尾插

(1)代码实现

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
	assert(phead);
	if (*phead == NULL)
	{
		*phead = SListCreatNode(x);//创建新节点并插入
	}
	else
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)//找到尾节点
		{
			tail = tail->next;
		}
		tail->next = SListCreatNode(x);//创建新节点并插入
	}
}

(2) 复杂度分析

  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：固定创造一个节点，空间复杂度为O(1)。

3.6 尾删

(1)代码实现

//6. 尾删
void  SListPopBack(SListNode** phead)
{
	assert(phead);
	assert(*phead);//链表为空就不进行尾删
	SListNode* tail = *phead;
	if (tail->next == NULL)//如果链表就只有一个元素就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

(2) 复杂度分析

  • 时间复杂度：需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.7 查找元素X

(1)代码实现

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	assert(phead);
	while (phead->next!=NULL)//注意最后一个节点是没有查找的
	{
		if (phead->data == x)
			return phead;
			phead = phead->next;
	}
	if (phead->data == x)
		return phead;//最后一个节点没有查找
	else
	return NULL;//没找到
}

(2) 时间复杂度

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.8 在pos位置修改

(1)代码实现


//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
	assert(pos);
	pos->data = x;
}

(2) 时间复杂度

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.9 在任意位置之前插入

(1)代码实现

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
	assert(phead);
	assert(*phead);
	if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
	{
		SListPushFront( phead,x);
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next  = pos;
	}
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.10 在任意位置删除

(1)代码实现

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
	assert(phead && *phead && pos);
	if (pos==*phead)//如果pos位置就是第一个节点就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

3.11 单链表的销毁

(1)代码实现

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
	assert(*phead && phead);
	SListNode* cur = *phead;
	while (cur!= NULL)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*phead = NULL;
}

(2) 复杂度分析

  • 时间复杂度：可能需要遍历整个链表，时间复杂度为O(N)。
  • 空间复杂度：不需要格外的空间消耗，空间复杂度为O(1)。

4. 完整代码

SList.c

#define _CRT_SECURE_NO_WARNINGS

#include"SList.h"

//1. 新节点的创建
SListNode*  SListCreatNode(SListDataType x)
{
	SListNode* NewNode= (SListNode*)malloc(sizeof(SListNode));//开辟空间
	if (NewNode == NULL)//判断空间是否开辟成功
	{
		perror("malloc fail");
		return NULL;
	}
	NewNode->data = x;//赋值
	NewNode->next = NULL;//置空
	return NewNode;
}

//2. 打印单链表
void PrintSList(SListNode* phead)
{
	if (phead == NULL)
	{
		printf("NULL");//如果链表没有元素就打印NULL
		return;
	}
	SListNode* cur = phead;
	//循环单链表打印
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//3. 头插
void SListPushFront(SListNode** phead, SListDataType x)
{
	assert(phead);
	SListNode* newnode =SListCreatNode(x);//创建一个新节点
	newnode->next =*phead;
	*phead = newnode;
}

//4. 头删
void  SListPopFront(SListNode** phead)
{
	assert(phead);
	assert(*phead);//如果没有数据就不用头删，并报错
	SListNode* cur = (*phead)->next;
	free(*phead);
	*phead = cur;
}

//5. 尾插
void SListPushBack(SListNode** phead, SListDataType x)
{
	assert(phead);
	if (*phead == NULL)
	{
		*phead = SListCreatNode(x);//创建新节点并插入
	}
	else
	{
		SListNode* tail = *phead;
		while (tail->next != NULL)//找到尾节点
		{
			tail = tail->next;
		}
		tail->next = SListCreatNode(x);//创建新节点并插入
	}
}

//6. 尾删
void  SListPopBack(SListNode** phead)
{
	assert(phead);
	assert(*phead);//链表为空就不进行尾删
	SListNode* tail = *phead;
	if (tail->next == NULL)//如果链表就只有一个元素就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

//7. 查找元素X
SListNode* SListFind(SListNode* phead, SListDataType x)
{
	assert(phead);
	while (phead->next!=NULL)//注意最后一个节点是没有查找的
	{
		if (phead->data == x)
			return phead;
			phead = phead->next;
	}
	if (phead->data == x)
		return phead;//最后一个节点没有查找
	else
	return NULL;//没找到
}

//8. 在pos位置修改
void SListModify( SListNode* pos, SListDataType x)
{
	assert(pos);
	pos->data = x;
}

//9. 在任意位置之前插入
void SListInsert(SListNode** phead, SListNode* pos, SListDataType x)
{
	assert(phead);
	assert(*phead);
	if (pos==*phead)//如果pos位置刚好是第一个节点就进行头插
	{
		SListPushFront( phead,x);
	}
	else
	{
		SListNode* newnode = SListCreatNode(x);
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = newnode;
		newnode->next  = pos;
	}
}

//10. 在任意位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
	assert(phead && *phead && pos);
	if (pos==*phead)//如果pos位置就是第一个节点就进行头删
	{
		SListPopFront(phead);
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != pos)//找到pos前一个节点
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

//11. 销毁单链表
void SListDestroy(SListNode** phead)
{
	assert(*phead && phead);
	SListNode* cur = *phead;
	while (cur!= NULL)
	{
		SListNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	*phead = NULL;
}

5. 完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

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

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

相关文章

深入解析CAS的原理机制

深入解析CAS的原理机制

一、基本概述 1.1 引入背景 例&#xff1a;i。假设由线程A和B需要对i进行加1的操作。线程A和线程B会分别从主内存中读取i值到自己的工作内存中。原本相加之后的值为3&#xff0c;但线程A和线程B分别加1后将值刷新到主内存&#xff0c;发现主内存的值为2&#xff0c;出现错误。…
阅读更多...
学c还行，学Python很累，还有其他语言适合我吗？

学c还行，学Python很累，还有其他语言适合我吗？

学c还行&#xff0c;学Python很累&#xff0c;还有其他语言适合我吗&#xff1f; 在开始前我分享下我的经历&#xff0c;我刚入行时遇到一个好公司和师父&#xff0c;给了我机会&#xff0c;一年时间从3k薪资涨到18k的&#xff0c; 我师父给了一些 电气工程师学习方法和资料&a…
阅读更多...
新建项目module,但想归到一个目录下面

新建项目module,但想归到一个目录下面

1. 想建几个module, 例如 component-base-service,component-config-service, 但是module多了会在CloudAction下面显示很多目录, 所以想把它们归到components模块下面去, 类似于下图的效果 2. 创建过程 右击CloudAction 新建 module -> 选maven类型 输入components, 建成后删…
阅读更多...
【目标检测经典算法】R-CNN、Fast R-CNN和Faster R-CNN详解系列二：Fast R-CNN图文详解

【目标检测经典算法】R-CNN、Fast R-CNN和Faster R-CNN详解系列二：Fast R-CNN图文详解

RCNN算法详解&#xff1a;【目标检测经典算法】R-CNN、Fast R-CNN和Faster R-CNN详解系列一&#xff1a;R-CNN图文详解 学习视频&#xff1a;Faster RCNN理论合集 Fast RCNN 概念辨析 1. RoI 在Fast R-CNN中&#xff0c;RoI&#xff08;Region of Interest&#xff0c;感兴…
阅读更多...
Spring多线程事务处理

Spring多线程事务处理

一、背景 本文主要介绍了spring多线程事务的解决方案&#xff0c;心急的小伙伴可以跳过上面的理论介绍分析部分直接看最终解决方案。 在我们日常的业务活动中&#xff0c;经常会出现大规模的修改插入操作&#xff0c;比如在3.0的活动赛事创建&#xff0c;涉及到十几张表的插入…
阅读更多...
使用DateUtil工具类偏移日期

使用DateUtil工具类偏移日期

使用DateUtil工具类偏移日期 一、依赖二、源码三、示例代码 一、依赖 <!--工具依赖--><dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.16</version></dependency>二、源码 …
阅读更多...
Python常用图片数据方法

Python常用图片数据方法

文章目录 1. 常用图片数据类型2. 图片的显示2.1 plt.imshow()2.2 使用 turtle 来绘制图片 3.图片ndarray数据的常用切片操作使用 cv2 来读取图片打印数据R G B 通道的获取BGR 转成 RGBcv2 不支持中文路径的解决方法 4 PIL.Image 转成 QImage 或 QPixmap 1. 常用图片数据类型 使…
阅读更多...
Android基础开发-通讯录的添加和查询

Android基础开发-通讯录的添加和查询

案例&#xff1a;往手机通讯录添加信息&#xff0c;输入姓名和手机号。 保存的手机的表&#xff1a;一共有两个&#xff0c;一个是主表&#xff0c;提供一个联系人id&#xff0c;另外是辅表&#xff0c;提供id对应的手机号和姓名。 普通操作&#xff1a;一个表一个表的添加 …
阅读更多...
【黑马程序员】python函数

【黑马程序员】python函数

文章目录 函数什么是函数为什么学习函数函数定义函数的传入参数函数的返回值返回值基础None返回值 函数说明文档函数的嵌套调用定义代码示例 全局变量和局部变量全局变量global变量局部变量 函数综合案例 函数 什么是函数 组织好的&#xff0c;可重复使用的、用来实现特定功能…
阅读更多...
【每日八股】Java基础经典面试题2

【每日八股】Java基础经典面试题2

前言&#xff1a;哈喽大家好&#xff0c;我是黑洞晓威&#xff0c;25届毕业生&#xff0c;正在为即将到来的秋招做准备。本篇将记录学习过程中经常出现的知识点以及自己学习薄弱的地方进行总结&#x1f970;。 本篇文章记录的Java基础面试题&#xff0c;适合在学Java基础的小白…
阅读更多...
设计模式系列之-策略模式(优化过多代码if…else)

设计模式系列之-策略模式(优化过多代码if…else)

首先解释下什么策略模式 如下图&#xff1a; 简而言之&#xff1a;算法的使用与算法的实现分离开来 想象有一个开关按钮&#xff0c;每次按下去都可以切换不同的灯光模式&#xff08;例如&#xff1a;强光、柔光、闪烁&#xff09;&#xff0c;这里的每种灯光模式就是一个策略…
阅读更多...
程序人生——Java中基本类型使用建议

程序人生——Java中基本类型使用建议

目录 引出Java中基本类型使用建议建议21&#xff1a;用偶判断&#xff0c;不用奇判断建议22&#xff1a;用整数类型处理货币建议23&#xff1a;不要让类型默默转换建议24&#xff1a;边界、边界、还是边界建议25&#xff1a;不要让四舍五入亏了一方 建议26&#xff1a;提防包装…
阅读更多...
Unity类银河恶魔城学习记录8-5 p81 Blackhole duration源代码

Unity类银河恶魔城学习记录8-5 p81 Blackhole duration源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码、 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Blackhole_Skill_Controller.cs using System.Collections; using Syste…
阅读更多...
UL1642标准_锂聚合物电池亚马逊测试报告

UL1642标准_锂聚合物电池亚马逊测试报告

UL1642标准_锂聚合物电池亚马逊测试报告 什么是锂聚合物电池UL1642标准&#xff1f; UL1642 认证要求涵盖旨在用于技术人员可更换或用户可更换应用的锂离子电池。UL1642 认证要求是为了避免锂离子电池在产品中工作时发生火灾或爆炸的风险。 锂聚合物电池 UL是Underwriters L…
阅读更多...
Devin：首位人工智能软件工程师的介绍

Devin：首位人工智能软件工程师的介绍

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
2024春招看了上百份程序员简历，这个工具写的简历最好！(附模板)

2024春招看了上百份程序员简历，这个工具写的简历最好！(附模板)

你们在制作简历时&#xff0c;是不是基本只关注两件事&#xff1a;简历模板&#xff0c;还有基本信息的填写。 当你再次坐下来更新你的简历时&#xff0c;可能会发现自己不自觉地选择了那个“看起来最好看的模板”&#xff0c;填写基本信息&#xff0c;却没有深入思考如何使简历…
阅读更多...
DataWhale公开课笔记2：Diffusion Model和Transformer Diffusion

DataWhale公开课笔记2：Diffusion Model和Transformer Diffusion

Stable Diffusion和AIGC AIGC是什么 AIGC的全称叫做AI generated content&#xff0c;AlGC (Al-Generated Content&#xff0c;人工智能生产内容)&#xff0c;是利用AI自动生产内容的生产方式。 在传统的内容创作领域中&#xff0c;专业生成内容&#xff08;PGC&#xff09;…
阅读更多...
Python数值方法在工程和科学问题解决中的应用

Python数值方法在工程和科学问题解决中的应用

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 随着计算机技术的不断发展&#xff0c;Python作…
阅读更多...
UI设计中的图标的分类，功能性图标

UI设计中的图标的分类，功能性图标

图标的分类 既然知道了图标的作用和重要性&#xff0c;那么接下来&#xff0c;就要进一步了解在工作中我们要设计哪些图标。图标可以划分成三种大类:功能性图标、装饰性图标、启动图标。 功能性图标 功能图标是具有指代意义且具有功能标识的图形&#xff0c;它不仅是一种图形&a…
阅读更多...
代码随想录算法训练营第day41|背包理论基础、416. 分割等和子集

代码随想录算法训练营第day41|背包理论基础、416. 分割等和子集

目录 a.背包理论基础——01背包 1.二维数组的01背包表示 2.一维滚动数组表示 b. 416. 分割等和子集 - 力扣&#xff08;LeetCode&#xff09; a.背包理论基础——01背包 背包问题分类&#xff1a; 对于面试的话&#xff0c;其实掌握01背包&#xff0c;和完全背包&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023