当前位置： 首页 > article >正文

C语言手撕链表，实现增删改查

article 2024/10/23 10:58:50

目录

前言

链表的概念与结构

单链表

        一、单链表结构 

         二、单链表创建节点

         三、单链表的打印

         四、单链表尾插

         五、单链表头插

         六、单链表尾删

         七、单链表头删

         八、单链表查找

        九、单链表指定位置插入 

        十、单链表指定位置删除 

 带头双向循环链表

         一、带头双向循环链表结构

        二 、带头双向循环链表初始化

        三、带头双向循环链表创建节点

        四、带头双向循环链表打印

        五、带头双向循环链表尾插

        六、带头双向循环链表头插

        七、带头双向循环链表尾删

        八、带头双向循环链表头删

        九、带头双向循环链表查找

        十、带头双向循环链表指定位置插入

        十一、带头双向循环链表指定位置删除

 链表算法题

 

前言

        数据结构的链表结构非常多样，总结起来一共有八种，虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表，因此此篇只会实现单链表和双向带头循环链表，其他链表都是大同小异的

        此篇顺序表基于博主自己的理解实现，如有错误之处，还望大家指出！

链表的概念与结构

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

        与顺序表不同的是，链表⾥的每个元素都是独⽴申请下来的空间，我们称之为“结点/结点”，我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点

 

        链表的性质 

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

单链表

        一、单链表结构 

//单链表节点结构的定义
struct slist
{
	//存储数据
	int data;
	//指向下一个元素的地址
	struct slist* next;
};

         二、单链表创建节点

        链表的结点⼀般是从堆上申请的，通过函数返回时不会被销毁，在创建节点时顺便进行初始化

//创造新节点
struct slist* buynode(int n)
{
	struct slist* node = (struct slist*)calloc(1, sizeof(struct slist));
	//初始化节点
	node->data = n;
	node->next = NULL;
	//申请失败
	if (node == NULL)
	{
		return NULL;
	}
	//返回节点
	return node;
}

         三、单链表的打印

        时间复杂度：O（ N ）

        通过传递过来的头节点依次向后打印，直到找到尾节点，因此时间复杂度为O（ N ）

//打印
void slistprintf(struct slist* cur)
{
	//依次向后打印，直到找到尾节点
	while (cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

         四、单链表尾插

        时间复杂度：O（ N ）

        单链表的尾插，需要先遍历链表，找到尾节点，因此时间复杂度为O（ N ）

        函数的形参需要使用二级指针来接收，因为当链表为空时我们需要改变外部的实参为新创建的节点

//尾插
void slistpushback(struct slist** p, int n)
{
	//创造节点
	struct slist* node = buynode(n);
	//链表为空
	if (*p == NULL)
	{
		*p = node;
	}
	//链表不为空
	else
	{
		//寻找尾部节点
		struct slist* cur = *p;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		//在尾部节点插入节点
		cur->next = node;
	}
	
}

         五、单链表头插

         时间复杂度：O（ 1 ）

        与顺序表不同，表不需要移动元素，可以直接在头部插入 ，因此时间复杂度为O（ 1 ）

       函数的形参需要使用二级指针来接收，因为当链表为空时我们需要改变外部的实参为新创建的节点 

//头插
void slistpushtop(struct slist** p, int n)
{
	//创建节点
	struct slist* cur = buynode(n);
	//在头部插入一个节点
	cur->next = *p;
	//指向新的头节点
	*p = cur;
	
}

         六、单链表尾删

         时间复杂度：O（ N ） 

         单链表的尾删，需要先遍历链表，找到尾节点，因此时间复杂度为O（ N ）

        函数的形参需要使用二级指针来接收，因为当链表元素个数为1时我们需要改变外部的实参为NULL

//尾删
void slistpopback(struct slist** p)
{
	struct slist* cur = *p;
	//如果链表为空直接返回
	if (*p == NULL)
	{
		return;
	}
	//如果链表中只有一个元素
	//直接释放，头节点置为空
	if (cur->next == NULL)
	{
		free(*p);
		*p = NULL;
	}
	else
	{
		//寻找尾节点的前一个节点
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		//释放尾节点
		free(cur->next);
		//尾节点的前一个节点的下一个元素置为空
		cur->next = NULL;
	}
}

         七、单链表头删

          时间复杂度：O（ 1 ）

        可以直接在头部删除 ，因此时间复杂度为O（ 1 ）

        函数的形参需要使用二级指针来接收，因为当链表元素个数为1时我们需要改变外部的实参为NULL 

//头删
void slistpoptop(struct slist** p)
{
	//链表不能为空
	if (*p == NULL)
	{
		return;
	}
	//保存当前头节点
	struct slist* cur = *p;
	//将头节点改变为当前头节点的下一个节点
	*p = (*p)->next;
	//释放旧的头节点
	free(cur);
}

         八、单链表查找

         时间复杂度：O（ N ） 

         需要先遍历链表，一一对比，因此时间复杂度为O（ N ）

//查找
struct slist* slistfind(struct slist* p, int n)
{
	//链表不能为空
	if (p == NULL)
	{
		return NULL;
	}
	//遍历链表，寻找
	while (p != NULL)
	{
		//找到了，返回节点
		if (p->data == n)
		{
			return p;
		}
		p = p->next;
	}
	//没找到，放回空
	return NULL;
	
}

        九、单链表指定位置插入 

         时间复杂度：O（ N ）

         想要在指定位置插入数据，需要先找到指定位置之前的节点，最好情况为头插时间复杂度为O（ 1 ），最坏情况下为尾插时间复杂度为O（ N ），因此综合来说时间复杂度为O（ N ）

         函数的形参需要使用二级指针来接收，因为当插入的位置为头部时我们需要改变外部的实参为新创建的节点 

//在指定位置之前插入一个元素
void slistinsert(struct slist** p, struct slist* pos, int n)
{
	//插入的位置不能为空
	if (pos == NULL)
	{
		return;
	}
	//创建节点
	struct slist* node = buynode(n);
	
	struct slist* cur = *p;
	//在头节点之前插入节点
	if (cur == pos)
	{
		node->next = *p;
		*p = node;
	}
	else
	{
		//寻找指定位置之前的节点
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		node->next = cur->next;
		cur->next = node;
		
	}
}

        十、单链表指定位置删除 

         时间复杂度：O（ N ）

        想要在指定位置删除数据，需要先找到指定位置之前的节点，最好情况为头删时间复杂度为O（ 1 ），最坏情况下为尾珊时间复杂度为O（ N ），因此综合来说时间复杂度为O（ N ） 

         函数的形参需要使用二级指针来接收，因为当删除的位置为头部时我们需要改变外部的实参为头节点的下个节点

//删除指定位置的节点
void slisterase(struct slist** p, struct slist* pos)
{
	//链表不能为空
	if (pos == NULL)
	{
		return;
	}
	struct slist* cur = *p;
	//删除的节点是头节点
	if (cur == pos)
	{
		*p = pos->next;
	}
	else
	{
		//寻找指定位置之前的节点
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		//将指定位置之前节点的下一个节点指向删除节点的下一个
		cur->next = pos->next;
	}
	//释放要删除的节点
	free(pos);
}

 带头双向循环链表

        这⾥的“带头”跟单链表的“头节点”是两个概念，带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”

        “哨兵位”存在的意义：

        1、遍历循环链表避免死循环

        2、我们在进行增删操作时链表的哨兵位是不会改变的，就不需要考虑到二级指针接收的情况

         一、带头双向循环链表结构

//双向带头循环链表
struct dlist
{
	int data;//存储数据
	struct dlist* prev;//上一个节点
	struct dlist* next;//下一个节点
};

        二 、带头双向循环链表初始化

        创造哨兵位实现链表循环

//链表初始化
struct dlist* initdlist()
{
	//创建哨兵位节点
	struct dlist* node = (struct dlist*)malloc(sizeof(struct dlist));
	//实现循环链表
	node->next = node;
	node->prev = node;
	//返回哨兵位节点
	return node;
}

        三、带头双向循环链表创建节点

         链表的结点⼀般是从堆上申请的，通过函数返回时不会被销毁，在创建节点时顺便进行初始化

//创建节点
struct dlist* buy_dlist_node(int val)
{
	//创建节点
	struct dlist* node = (struct dlist*)calloc(1, sizeof(struct dlist));
	//保存数据
	node->data = val;
	//初始化为空
	node->next = NULL;
	node->prev = NULL;
	//返回节点
	return node;
}

        四、带头双向循环链表打印

         时间复杂度：O（ N ）

        与单链表不同，带头双向循环链表判断是否到尾节点的方式为判断当前节点是否为哨兵位

//打印链表
void dlistprintf(struct dlist* head)
{
	if (head->next == NULL)
	{
		return;
	}
	//跳过哨兵位，找头节点
	struct dlist* cur = head->next;
	//当前节点不为哨兵位
	while (cur != head)
	{
		printf("%d ", cur->data);   
		cur = cur->next;
	}
	printf("\n");
}

        五、带头双向循环链表尾插

         时间复杂度：O（ 1 ）

        带头双向循环链表的尾插，不需要先遍历链表，找到尾节点，因为有循环的因素哨兵位的上一个节点就是尾节点，因此时间复杂度为O（ 1 ） 

//尾插，在哨兵为之前插入，在哨兵位之后插入为头插
//哨兵位节点的位置是不会改变的，所以不需要使用二级指针
void dlistpushback(struct dlist* head, int x)
{
	//创建节点
	struct dlist* node = buy_dlist_node(x);
	//寻找尾节点，哨兵位的上一个节点就是尾节点
	struct dlist* tail = head->prev;
	//新节点的下一个为哨兵位
	node->next = head;
	//新节点的上一个为旧的尾节点
	node->prev = tail;

	//设置哨兵位的上一个节点为新的尾节点
	head->prev = node;
	//新尾节点的下一个为哨兵位
	tail->next = node;
}

        六、带头双向循环链表头插

         时间复杂度：O（ 1 ）

        直接在哨兵位的后面插入 ，因此时间复杂度为O（ 1 ），因为有循环的因素所以这里在哨兵位之前插入为尾插

//头插，在哨兵位之后插入，在哨兵位之前插入为尾插
void dlistpushfront(struct dlist* head, int x)
{
	//创建节点
	struct dlist* node = buy_dlist_node(x);
	//寻找头节点，哨兵位的下一个节点就是头节点
	struct dlist* cur = head->next;
	//新节点的下一个为头节点
	node->next = cur;
	//新节点的上一个为哨兵位
	node->prev = head;

	//哨兵位的下一个为新节点
	head->next = node;
	//头节点的上一个为新节点
	cur->prev = node;
}

        七、带头双向循环链表尾删

         时间复杂度：O（ 1 ） 

          带头双向循环链表的尾删，不需要先遍历链表，找到尾节点，因为有循环的因素哨兵位的上一个节点就是尾节点，因此时间复杂度为O（ 1 ） 

//尾删
void dlistpopback(struct dlist* head)
{
	//寻找尾节点，哨兵位的上一个节点就是尾节点
	struct dlist* tail = head->prev;
	//尾节点不能为哨兵位
	if (tail == head)
	{
		return;
	}
	//尾节点的上一个节点的下一个节点为哨兵位
	tail->prev->next = head;
	//哨兵位的上一个节点为尾节点的上一个
	head->prev = tail->prev;
	//释放尾节点
	free(tail);
}

        八、带头双向循环链表头删

         时间复杂度：O（ 1 ） 

        哨兵位的下一个就是头节点 

//头删
void dlistpopfront(struct dlist* head)
{
	//寻找头节点，哨兵位的下一个节点就是头节点
	struct dlist* cur = head->next;
	//头节点不能为哨兵位
	if (cur == head)
	{
		return;
	}
	//哨兵位的下一个节点为头节点的下一个
	head->next = cur->next;
	//头节点的下一个节点的上一个节点为哨兵位
	cur->next->prev = head;
	//释放头节点
	free(cur);
}

        九、带头双向循环链表查找

        时间复杂度：O（ N ） 

        需要先遍历链表，一一对比，因此时间复杂度为O（ N ） 

//查找
struct dlist* dlistfind(struct dlist* head, int x)
{
	//寻找头节点，哨兵位的下一个节点就是头节点
	struct dlist* cur = head->next;
	//遍历寻找
	while (cur != head)
	{
		if (cur->data == x)
		{
			//找到返回地址
			return cur;
		}
		cur = cur->next;
	}
	//找不到返回空
	return NULL;
}

        十、带头双向循环链表指定位置插入

        时间复杂度：O（ 1 ） 

        有区别于单链表， 带头双向循环链表，不需要寻找指定节点的前一个节点，prev 中保存的就是指定节点的前一个节点，因此时间复杂度为O（ 1 ）

//任意位置插入 ( 之后 )
void dlistinsert(struct dlist* pos, int x)
{
	//插入节点不能为空
	if (pos == NULL)
	{
		return;
	}
	//创建节点
	struct dlist* node = buy_dlist_node(x);
	//指定位置的下一个节点的上一个为新节点
	pos->next->prev = node;
	//新节点的下一个为指定位置的下一个
	node->next = pos->next;

	//指定位置的下一个为新节点
	pos->next = node;
	//新节点的上一个为指定位置
	node->prev = pos;
	
}

        十一、带头双向循环链表指定位置删除

         时间复杂度：O（ 1 ） 

         带头双向循环链表，不需要寻找指定节点的前一个节点，prev 中保存的就是指定节点的前一个节点，因此时间复杂度为O（ 1 ） 

//任意位置删除
void dlisterase(struct dlist* pos)
{
	//删除节点不能为空
	if (pos == NULL)
	{
		return;
	}
	//删除节点的上一个的下一个为删除节点的下一个
	pos->prev->next = pos->next;
	//删除节点的下一个的上一个为删除节点的上一个
	pos->next->prev = pos->prev;
	//释放节点
	free(pos);
}

 链表算法题

        总体而言初学链表时是比较抽象的，在算法题中有助于帮助我们对链表的理解 

        1、移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/description/
        2、反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
        3、链表的中间结点
https://leetcode.cn/problems/middle-of-the-linked-list/description/
        4、合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/description/
        5、链表分割
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70
        6、链表的回⽂结构
https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa
        7、相交链表
https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

 


http://www.kler.cn/news/361469.html

相关文章：

  • 使用JUC包的AtomicXxxFieldUpdater实现更新的原子性
  • R语言机器学习算法实战系列（九）决策树分类算法 (Decision Trees Classifier)
  • Golang 并发编程入门：Goroutine 简介与基础用法
  • Vehicle Spy3.9如何新建工程—总览
  • Unable to open nested entry ‘********.jar‘ 问题解决
  • jetson nano ubuntu20.04安装ros-Noetic
  • 龙芯+FreeRTOS+LVGL实战笔记（新）——12按键输入初步
  • Spring Boot框架的大创项目文档管理系统
  • 【从零开始的LeetCode-算法】3184. 构成整天的下标对数目 I
  • Qt项目实战：图片轮播器
  • NC 单据模板自定义项 设置参照（自定义参照）
  • 【硬件问题】——显示器黑屏且只显示鼠标
  • 工具类的构造方法为什么要用private修饰
  • Linux安装最新docker（CentOS 7.6）
  • Github 2024-10-23C开源项目日报 Top10
  • 登录后端笔记（一）：注册、登录；基于MD5加密
  • 思迅商云8采购单和批发单可以重复输入一样的货号，用于区别不同生产日期的同样商品的。
  • Java项目实战II基于Spring Boot的毕业就业信息管理系统设计与实现(源码+数据库+文档)
  • Spring Boot：为中小型医院网站提速
  • 在 Spring 中使用 @EhCache 注解作为缓存
  • 2023年五一杯数学建模C题双碳目标下低碳建筑研究求解全过程论文及程序
  • 武汉融资融券开户佣金最低是多少？哪家证券交易两融利率最低？
  • 数据结构修炼——常见的排序算法：插入/希尔/选择/堆排/冒泡/快排/归并/计数
  • 1 -《本地部署开源大模型》如何选择合适的硬件配置
  • OpenR框架深度解读 - OpenAI启发的首个开源项目提升大型语言模型推理能力
  • 基于SpringBoot+Vue+uniapp微信小程序的社区门诊管理系统的详细设计和实现(源码+lw+部署文档+讲解等)