【数据结构和算法初阶(C语言)】链表-单链表（手撕详讲单链表增删查改）

目录

1.前言：顺序表回顾：

1.1顺序表的优缺点 

2.主角----链表

2.1链表的概念

2.2定义一个单链表的具体实现代码方式

3.单链表对数据的管理----增删查改

3.1单链表的创建

3.2单链表的遍历实现

3.2.1利用遍历实现一个打印我们链表内容的函数的函数 

3.3头插法----从头部插入数据实现

3.4尾插法---从尾部插入数据

3.5尾删法-----从尾部删除数据

3.6头删法

3.7寻找函数 

3.8修改函数

3.9在pos位置前插入

3.10在pos位置后插入

3.11在pos位置前删除

3.12在pos位置后一个位置删除

3.13在pos位置删除

4.补充链表类型暂时了解 

5.结语 

1.前言：顺序表回顾：

顺序表知识回顾

1.1顺序表的优缺点 

  • 优点：

        1.尾插、尾删速度足够快

        2.可以使用下标来进行随机访问和数据修改

  • 缺点：

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

        2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。比如我们realloc增添空间还会涉及到原始空间数据的拷贝和原始空间的释放。

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

               

为了解决单链表的这缺点，于是我们引入了链表，链表优点（可以按需申请空间）

2.主角----链表

（今天重要讲解单链表），链表具有八种结构

2.1链表的概念

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

2.2单链表的结构演示

在数据结构中，我们往往会以创建结构体的方式来实现链表，在结构体中定义至少定义两个成员：一个保存我们当前节点的数据，我们称为数据域，另外一个成员保存下一个节点的地址，我们称为指针域。

从上图，我们就可以发现，链式结构在逻辑上是连续的就是我们可以通过指针顺序找到链表中的每个节点但是，在物理上不一定连续，因为我们每一个节点的空间都是通过malloc在堆上申请开辟的空间，那么地址可能不连续。

2.2定义一个单链表的具体实现代码方式

typedef int SLTDataType;


typedef struct SListNode
{
	SLTDataType  data;//数据领域
	struct SListNode* next;//定义指针领域，方便保存下一个节点的地址

}SLNode;

为了后期使用方便，我把整型这个类型重新定义了一下，后续如果需要改变我们这个程序中的数据类型，比如换成doubble类型，我们换一下宏定义就好。

 

3.单链表对数据的管理----增删查改

3.1单链表的创建

有了结构体类型，那我们就可以创建一个单链表：

1.首先我们先创建一个节点，由于后续插入等等操作都要创建节点，这里我们就可以将节点创建过程分装为一个函数：

SLNode* BuySListNode(SLTDataType x)
{
	//首先为我们的节点申请空间，创建一个节点，就申请这个结构体类型那么大的一个空间就行
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	//判断一下是否开辟成功
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	//开辟成功，就初始化这个节点
	newnode->data = x;
	newnode->next = NULL;
	return newnode;//返回节点地址
}

2.然后我们将每个节点链接起来，通个指针和每个节点的地址，这里就涉及头部插入数据和尾部插入数据，我们放在下面实现：

3.2单链表的遍历实现

3.2.1利用遍历实现一个打印我们链表内容的函数的函数 

void SLPrint(SLNode* phead)
{
	
	SLNode* cur = phead;
	while (cur)
	{
		printf("%d ->", cur->data);
		cur = cur->next;//指针移动到下一个节点
	}
	printf("NULL");
	
}

 

3.3头插法----从头部插入数据实现

首先，我们先定义准备一个头指针，用于保存我们链表第一个节点的地址，，方便我们后期使用整块链表。

然后，当我们还没有链表，这时候放入第一个节点：

我们把节点地址给我们的头指针就好。

2.当我们的头指针不为空，这时要插入数据

应该将第一个节点的地址赋值给newnode的next,然后将我们newnode节点作为我们的心的头结点将地址给头指针。

两种情况可以视为一种情况，只是第一种特殊一下，我们的头指针指向空。

注意：在我们写头插函数的时候，传递的是头指针的地址，我们在函数中解引用操作操作的是原先的指针，这样才能整体使用我们的空间，如果我们只是传指针，那么在我们的头插函数中的头指针，只是我们真正头指针的一份拷贝，这样函数结束，形参就销毁，虽然空间开辟了，但是调用结束我们使用的还是原来没插入前的空间。



void SListPushBack(SLNode** phead,int x)
{
	SLNode* newnode = BuySListNode(x);
	newnode->next = *phead;
	*phead = newnode;

}

3.4尾插法---从尾部插入数据

 

当我们还没有链表，这时候放入第一个节点：

两种情况实现：

void SLTPushBack(SLNode** phead, SLTDataType x)
{
	SLNode* newnode = BuySListNode(x);//创建新节点
	if (*phead == NULL)
	{
		newnode->next = *phead;
		*phead = newnode;

	}
	else
	{
		SLNode* cur =*phead;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = newnode;

	}

}

3.5尾删法-----从尾部删除数据

  • ①当我们没有链表此时没有删除的东西，所以不能传入空指针
  • ②当我们只有一个节点要删除

那么由于我们头指针有所改变，所以函数传参还是传递我们的头指针的地址

  • ③当有很多节点

尽量不用->next->next=NULl的形式做判断，当只有一个节点的时候越界访问。 

实现一下：
 

void SLTPopBack(SLNode** phead)
{
	assert(*phead);//头指针不能为空
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLNode* bfend = NULL;
		SLNode* end = *phead;
		while (end->next)
		{
			bfend = end;
			end = end->next;
		}
		free(bfend->next);
		bfend->next = NULL;

	}
}

3.6头删法

void SLTPopFront(SLNode** phead)
{
	assert(*phead);
	//当头指针非空
	SLNode* newnode =(*phead)->next;
	
	(*phead)->next = NULL;
	free(*phead);
	*phead = newnode;
}

 

3.7寻找函数 

遍历寻找某个值

SLNode* SLFind(SLNode* phead, SLTDataType x)
{
	SLNode* cur = phead;

	
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;

	}
	
	return NULL;


}

3.8修改函数

找到值返回对应位置的指针，然后通过指针修改

void  SLMod(SLNode* phead)
{
	int x = 0;
	printf("请输入你要修改的值：\n");
	scanf("%d", &x);
	SLNode* ret = SLFind(phead, x);
	if (ret)
	{
		printf("请输入你要修改成什么值\n");
		int c = 0;
		scanf("%d", &c);
		ret->data = c;
	}
}

3.9在pos位置前插入

涉及到头插，就要涉及头指针的改变，那么我们就要传二级指针：

void SLTInsert(SLNode** phead, SLNode* pos, SLTDataType x)
{
	//不能传入空指针
	assert(pos);
	if (pos == *phead)//头插
	{
		SListPushBack(phead, x);
	}
	else
	{
		//先遍历到要插入的位置前一个
		SLNode* pre = *phead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		//然后插入这个新节点，开辟新节点
		SLNode* newnode = BuySListNode(x);
		pre->next = newnode;
		newnode->next = pos;


	}
}

3.10在pos位置后插入

不是不能和头指针相等，是不能为空指针。不可能实现头插

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

 

3.11在pos位置前删除

3.12在pos位置后一个位置删除

void SLTEraseAfter(SLNode* pos)
{
	//不能传空指针、头指针、和指向尾节点的指针，没有意义
	assert(pos);
	assert(pos->next);
	SLNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;
}

3.13在pos位置删除

void SLTErase(SLNode** phead, SLNode* pos)
{
	assert(pos);//断言不会传入空指针
	if (pos == *phead)
	{
		//头删
		SLTPopFront(phead);
	}
	else
	{
		SLNode* pre = *phead;
		while (pre->next != pos)
		{
			pre - pre->next;
		}
		pre->next = pos->next;
		free(pos);
		pos = NULL;

	}
}

4.补充链表类型暂时了解 

① 单向或者双向

②带头或者不带头

③循环或者非循环

5.结语 

今天的重点在于理解单链表的增删查改，特别是什么时候需要传输二级指针，什么时候不传。以上就是本期的所有内容，知识含量蛮多，大家可以配合解释和原码运行理解。创作不易，大家如果觉得还可以的话，欢迎大家三连，有问题的地方欢迎大家指正，一起交流学习，一起成长，我是Nicn，正在c++方向前行的奋斗者，数据结构内容持续更新中，感谢大家的关注与喜欢。

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

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

相关文章

LeetCode——栈和队列（Java）

LeetCode——栈和队列（Java）

栈和队列 简介[简单] 232. 用栈实现队列[简单] 225. 用队列实现栈[简单] 20. 有效的括号[简单] 1047. 删除字符串中的所有相邻重复项[中等] 150. 逆波兰表达式求值[困难] 239. 滑动窗口最大值[中等] 347. 前 K 个高频元素 简介 记录一下自己刷题的历程以及代码。写题过程中参考…
阅读更多...
【Linux】进程优先级以及Linux内核进程调度队列的简要介绍

【Linux】进程优先级以及Linux内核进程调度队列的简要介绍

进程优先级 基本概念查看系统进程修改进程的优先级Linux2.6内核进程调度队列的简要介绍和进程优先级有关的概念进程切换 基本概念 为什么会存在进程优先级？   进程优先级用于确定在资源竞争的情况下，哪个进程将被操作系统调度为下一个运行的进程。进程…
阅读更多...
Linux设备模型(七) - Netlink

Linux设备模型(七) - Netlink

一，什么是netlink通信机制 Netlink套接字是用以实现用户进程与内核进程通信的一种特殊的进程间通信(IPC) ,也是网络应用程序与内核通信的最常用的接口。Netlink 是一种特殊的 socket，它是 Linux 所特有的。 Netlink 是一种在内核与用户应用间进行双向数…
阅读更多...
PCB：多CAN口的信号转接板

PCB：多CAN口的信号转接板

背景 在测试多路CAN口时，需要频繁更换接口引脚，从而接入CAN收发器。为了提升测试效率，可以设计一个简易多路CAN收发器转接板。PCB板子一端是40脚母口，另一端是10路CAN螺钉式接线端子，自带电池减少接线。 分配空闲时间…
阅读更多...
网络编程：基于TCP和UDP的服务器、客户端

网络编程：基于TCP和UDP的服务器、客户端

1.基于TCP通信服务器 程序代码&#xff1a; 1 #include<myhead.h>2 #define SER_IP "192.168.126.121"//服务器IP3 #define SER_PORT 8888//服务器端口号4 int main(int argc, const char *argv[])5 {6 //1.创建用于监听的套接字7 int sfd-1;8 sf…
阅读更多...
Sora：开启视频生成新时代的强大人工智能模型

Sora：开启视频生成新时代的强大人工智能模型

目录 一、Sora模型的诞生与意义 二、Sora模型的技术特点与创新 三、Sora模型的应用前景与影响 四、面临的挑战与未来发展 1、技术挑战 2、道德和伦理问题 3、计算资源需求 4、未来发展方向 随着信息技术的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;已成为…
阅读更多...
Unity（第九部）物体类

Unity（第九部）物体类

拿到物体的某些数据 using System.Collections; using System.Collections.Generic; using UnityEngine;public class game : MonoBehaviour {// Start is called before the first frame updatevoid Start(){//拿到当前脚本所挂载的游戏物体//GameObject go this.gameObject;…
阅读更多...
Python算法100例-2.10 马克思手稿中的数学题

Python算法100例-2.10 马克思手稿中的数学题

完整源代码项目地址&#xff0c;关注博主私信源代码后可获取 1.问题描述2.问题分析3.算法设计4.确定程序框架5.完整的程序6.运行结果 1&#xff0e;问题描述 马克思手稿中有一道趣味数学问题&#xff1a;有30个人&#xff0c;其中有男人、女人和小孩&#xff0c;他们在同一家…
阅读更多...
C语言基础18 循环

C语言基础18 循环

们可能需要多次执行同一块代码。一般情况下&#xff0c;语句是按顺序执行的&#xff1a;函数中的第一个语句先执行&#xff0c;接着是第二个语句&#xff0c;依此类推。 编程语言提供了更为复杂执行路径的多种控制结构。 循环语句允许我们多次执行一个语句或语句组&#xff0…
阅读更多...
小红书的几种赚钱方式解读

小红书的几种赚钱方式解读

小红书的七种变现方式&#xff1a; 1.通过小红书蒲公英平台接广告&#xff0c;粉丝数量大于1000的用户可以开通。单条笔记的广告费用从几百元到几十万不等。 2.开设小红书专栏&#xff0c;粉丝数量大于1万的用户可以开通。 3.进行私域变现&#xff0c;将小红书的咨询引导到微信…
阅读更多...
Java 小项目开发日记 03（文章分类接口的开发）

Java 小项目开发日记 03（文章分类接口的开发）

Java 小项目开发日记 03&#xff08;文章分类接口的开发&#xff09; 项目目录 配置文件&#xff08;pom.xml&#xff09; <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocat…
阅读更多...
内核打印应用程序出错信息，DEBUG_USER

内核打印应用程序出错信息，DEBUG_USER

前言 在 Linux 系统中&#xff0c;运行一个应用程序&#xff0c;突然提示段错误&#xff0c;并停止运行 # ./crash.out Segmentation fault如果这个时候操作系统能多提示点错误信息&#xff0c;那将会缩短我们 debug 的时间。 core dump 就是一个办法&#xff0c;可以查看我…
阅读更多...
javaWeb学习04

javaWeb学习04

AOP核心概念: 连接点: JoinPoint, 可以被AOP控制的方法 通知: Advice 指哪些重复的逻辑&#xff0c;也就是共性功能(最终体现为一个方法) 切入点: PointCut, 匹配连接点的条件&#xff0c;通知仅会在切入点方法执行时被应用 目标对象: Target, 通知所应用的对象 通知类…
阅读更多...
nginx（三）实现反向代理客户端 IP透传

nginx（三）实现反向代理客户端 IP透传

正常情况下&#xff0c;客户端去访问代理服务器&#xff0c;然后代理服务器再取访问真实服务器&#xff0c;在真实服务器上&#xff0c;只能显示代理服务器的ip地址&#xff0c;而不显示客户端的ip地址&#xff0c;如果想让客户端的ip地址也能在真实服务端看见&#xff0c;这一…
阅读更多...
数仓开发环境链接

数仓开发环境链接

这里写目录标题 1开发工具链接大数据组件1.1 启动hiveserver21.2配置DataGrip连接1.3测试使用 2 环境问题排查思路 1开发工具链接大数据组件 1.1 启动hiveserver2 数仓开发工具datagrip 需要用到JDBC协议链接到Hive&#xff0c;需要启动hiveserver2。 cd /opt/module/hive h…
阅读更多...
string 类 经典习题之数字字符相加

string 类 经典习题之数字字符相加

题目&#xff1a; 给定两个字符串形式的非负整数 num1 和num2 &#xff0c;计算它们的和并同样以字符串形式返回。 你不能使用任何內建的用于处理大整数的库&#xff08;比如 BigInteger&#xff09;&#xff0c; 也不能直接将输入的字符串转换为整数形式。 题目来源&#xff1…
阅读更多...
进程2月29日

进程2月29日

题目&#xff1a;要求将当前路径下&#xff0c;所有文件的权限及最后一次的访问时间提取出来&#xff0c;写入到file.txt中。&#xff08;提示:opendir readir stat -->提取出来的数据写入到file.txt中&#xff09; 代码&#xff1a; #include <stdio.h> #include &…
阅读更多...
C语言：数据在内存中的存储

C语言：数据在内存中的存储

C语言&#xff1a;数据在内存中的存储 整数存储原码、反码、补码转换规则数据与内存的关系 大小端字节序浮点数存储IEEE 754标准存储过程取用过程 数据的存储范围 整数存储 原码、反码、补码 整数的2进制表示方法有三种&#xff0c;即原码、反码和补码 三种表示方法均有符号位…
阅读更多...
使用Python操作SQLite数据库

使用Python操作SQLite数据库

大家好&#xff0c;在数据涌现的今天&#xff0c;数据库已成为生活中不可或缺的工具。Python作为一种流行的编程语言&#xff0c;内置了多种用于操作数据库的库&#xff0c;其中之一就是SQLite。SQLite是一种轻量级的关系型数据库管理系统&#xff0c;它在Python中的应用非常广…
阅读更多...
http模块学习

http模块学习

http模块 客户端&#xff1a;负责消费资源的电脑 服务器&#xff1a;负责对外提供网络资源的电脑&#xff0c;与普通电脑的区别就在于服务器上 安装了web服务器软件。 http模块是Node.js官方提供用来 创建web服务器的模块&#xff0c;通过http模块提供的http.createServer()方…
阅读更多...
最新文章

Copyright @ 2022~2023