C语言链表超详解

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

✅作者简介嵌入式入坑者与大家一起加油希望文章能够帮助各位
📃个人主页@rivencode的个人主页
🔥系列专栏玩转数据结构
💬推荐一款模拟面试、刷题神器从基础到大厂面试题👉点击跳转刷题网站进行注册学习

目录

一.顺序表与链表的对比

在这里插入图片描述

  • 线性表
    线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列等线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构存储结构上并不一定是连续的线性表在物理上存储时通常以顺序表和链式结构的形式存储。

  • 线性表的顺序存储—>顺序表
    是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。

  • 线性表的链式存储
    线性表中的数据结点在内存中的位置是任意的即逻辑上相邻的数据元素在物理位置内存存储的位置上不一定相邻。

链式存储结构的优点

  • 空间利用率高需要一个空间就分配一个空间
  • 数据元素的逻辑次序靠节点的指针来指示插入和删除时不需要移动数据结点,任意位置插入删除时间复杂度为O(1)

链式存储结构的缺点

  • 存储密度小每个结点的指针域需要额外占用存储空间。当每个结点的数据域所占字节不多时指针域所占空间的比重显得很大存储密度大空间利用率越大。

在这里插入图片描述顺序表因为只有数据域没有指针域所以它的存储密度为最大1
不过这个问题一个结点也就多几个指针最多8个字节所以若是在现代计算机这点空间已经不算什么不过如果是像单片机这种嵌入式设备内存较小所以还是会有一点点影响的

  • 链式存储结构是非随机存取结构对任一结点的操作都要从头指针依次查找到该节点算法复杂度较高。

顺序表的优点

  • 存储密度为1最高因为没有指针域空间利用率高
  • 随机存取按位置访问元素的时间复杂度为O(1)直接根据数组下标访问元素

顺序表的缺点

  • 动态顺序表增容会付出一定性能消耗其次可能还是会存在一定的空间浪费不可能扩容的刚刚好
  • 在头部或者中部左右的插入删除需要移动元素时间复杂度为O(N),效率低。
    在这里插入图片描述
    总结
    顺序表的缺点就是链表的优点而链表的缺点就是顺序表的优点所以说不能说链表一定就比顺序表高级我们要视情况而定。

二.单链表的介绍

  • 线性表的链式存储
    线性表中的数据结点在内存中的位置是任意的即逻辑上是线性的数据元素在物理位置内存存储的位置上不一定相邻。

在这里插入图片描述
结点为什么在内存中是随机存储的呢
因为我们产生一个结点要给他分配内存是动态分配出来的malloc而分配的结点的内存的地址是随机的所以结点的地址是随机的也就是说结点在内存中的存储是随机的。

单链表的一个结点
在这里插入图片描述
在这里插入图片描述
我们只要知道一个结构体的指针地址就能访问该结构体的成员如果成员里面又包含下一个结点结构体指针又可以访问下一个结点的成员
在这里插入图片描述

若基础不好的先请参考
《指针详解》
《结构体详解》
其实链表你把结构体与指针搞明白了链表真的随便拿捏。

三.单链表的基本操作

不带头结点单向不循序链表
在这里插入图片描述
当链表为空时头指针指向空当链表不为空时头指针必须指向第一个结点

打印链表

void SListPrint(SLTNode *phead)
{
	SLTNode *cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur=cur->next;
	}
	printf("NULL\n");
}

在这里插入图片描述

清空链表

//清空单链表

void SListClear(SLTNode **pphead)
{
	SLTNode *cur = *pphead;
	SLTNode *next = NULL;
	while (cur != NULL)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

在这里插入图片描述
如果要改变头指针的值虽然头指针是一个指针但是指针一样有它的地址如果在一个函数中要改变它的值照样要传头指针的地址在解引用改变头指针的值如果你只是值传递则传过去的只是该头指针的临时拷贝一旦出函数会自动销毁并不会影响头指针本身的值。

创建节点

SLTNode* CreateSListNode(SLTDataType x)
{
	SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	NewNode->data = x;
	NewNode->next = NULL;
	return NewNode;
}

因为插入元素时都先要创建一个新结点所以为了避免代码冗余将创建新结点单独封装成一个函数。

尾插结点

void SListPushBack(SLTNode **pphead, SLTDataType x)
{
	SLTNode*NewNode = CreateSListNode(x);
	//当链表为空
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail=tail->next;
		}
		tail->next = NewNode;
	}
	
}

在这里插入图片描述
不要写了if不写else搞得后面又插入一个结点

头插结点

//链表头部插入一个节点
void SListPushFront(SLTNode **pphead, SLTDataType x)
{
	SLTNode*NewNode = CreateSListNode(x);
	NewNode->next = *pphead;
	*pphead = NewNode;
}

在这里插入图片描述

尾删结点

void SListPopBack(SLTNode **pphead)
{
	//链表为空
	if (*pphead == NULL)
	{
		return;
	}
	//只有一个节点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有多个节点
	else
	{
		SLTNode*prev = NULL;
		SLTNode*tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}

}

有以下几种情况

  • 当链表为空

在这里插入图片描述

  • 只有一个结点
    在这里插入图片描述
  • 有多个结点
    在这里插入图片描述

头删结点

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

在这里插入图片描述

查找值为x的节点

查找值为x的节点并返回节点的指针

//查找值为x的节点并返回节点的指针
SLTNode * SListFind(SLTNode *phead, SLTDataType x)
{
	SLTNode *cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			//找到返回该结点指针
			return cur;
		}
		cur = cur->next;
	}
	//找不到返回NULL指针
	return NULL;
}

在pos前面插入一个结点

在pos指针指向的结点的前一个位置插入一个结点


//在pos指针前一个插入一个节点
void SListInsert(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{
	//pos在第一个节点相当与头插
	if (*pphead== pos)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode *NewNode = CreateSListNode(x);
		SLTNode *prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = NewNode;
		NewNode->next = pos;
	}
	
}

在这里插入图片描述

如果pos的位置是第一个结点则在第一个结点前一个插入结点则为头插直接调用头插的接口函数即可。

pos在其他位置
在这里插入图片描述

删除pos指针指向的结点

void SListErese(SLTNode **pphead, SLTNode *pos)
{
	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}

	else
	{
		SLTNode *prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next=pos->next;
		free(pos);
	}
		
}

一样的如果pos的位置是第一个结点则在第一个结点前一个删除结点则为头删直接调用头删的接口函数即可。

pos在其他位置
在这里插入图片描述

四.链表结构介绍

在这里插入图片描述

  • 头指针

头指针是指向链表中第一个结点(存储该节点的地址)。如果链表中有头结点则头指针指向头结点若链表中没有头结点则头指针指向链表中第一个数据结点。

  • 头结点
    头结点链表中第一个结点一般不存储任何数据若链表有头结点则头指针一直指向头指针。
    在这里插入图片描述
    头结点本身没有什么作用头结点就起到一个站岗的作用

链表带头结点的优点

当链表为空表时插入删除结点都是在头结点后面头结点指向了第一个带数据的结点。

当我们单链表无头结点时当我们头插头插的时候我们都需要移动头指针的位置指向新的第一个结点当链表为空时又要将头结点置NULL这些操作我们都需要去改变头指针的值而改变头指针要传头指针的地址的用二级指针来操作无疑是增加了编程的难度如果链表有头结点而头指针一直指向头结点不管是头删头插都是在头结点后面增加删除而头指针一直指向头结点不用发生改变只需要一级指针就搞定

  • 循环链表
    循环链表是一种头尾相接的链表最后一个结点的指针指向第一个结点
    在这里插入图片描述
    优点从表中任意一节点出发可找到表中其他结点

注意
循环链表中没有NULL指针故遍历链表时其终止条件是判断是不是等于头指针。

  • 双向链表
    前面我们用单链表如果我们知道一个结点但我们不能直接找到该结点前面的一个结点。

所以双向链表在单链表的每一个结点再增加一个指向其直接前驱的指针域prev这样链表中就形成了有两个方向不同的链
在这里插入图片描述

  • 单向不带头不循环
    在这里插入图片描述

  • 单向带头不循环
    在这里插入图片描述

  • 单向不带头循环
    在这里插入图片描述

  • 单向带头循环
    在这里插入图片描述

  • 双向不带头不循环
    在这里插入图片描述
    prev的值也为空

  • 双向不带头循环
    在这里插入图片描述

  • 双向带头不循环
    在这里插入图片描述
    prev的值也为空

  • 双向带头循环
    在这里插入图片描述

五.双向带头循环链表

创建结点

ListNode*CreateListNode(LTDataType x)
{
	ListNode*NewNode = (ListNode*)malloc(sizeof(ListNode));
	NewNode->data = x;
	NewNode->next = NULL;
	NewNode->prev = NULL;
	return NewNode;
}

一个新的结点先将nextprev置空

链表初始化

//链表初始化
ListNode *ListInit()
{
	ListNode*phead = CreateListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

空表
在这里插入图片描述

销毁链表

void ListDestory(ListNode**pphead)
{
	ListNode*cur = (*pphead)->next;
	while (cur != *pphead)
	  {
		  ListNode* next = cur->next;
		  free(cur);
		  cur = next;
	  }
	free(*pphead);
	  *pphead = NULL;
}

在这里插入图片描述

清空链表

//清空链表
void ListClear(ListNode*phead)
{
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	phead->next = phead;
	phead->prev = phead;
}

只清空的话不需要释放头结点不过要将头结点的两个指针域都指向自己回到空表状态

打印链表

//打印链表
void Listprint(ListNode*phead)
{
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		printf("%d ",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

遍历是看是否遍历到了头结点才停下来。

尾插结点

//尾插
void ListPushBack(ListNode*phead, LTDataType x)
{
	 assert(phead != NULL);
	 ListNode*NewNode = CreateListNode(x);
	 ListNode*tail = phead->prev;
	 tail->next = NewNode;
	 NewNode->prev = tail;
	 NewNode->next = phead;
	 phead->prev = NewNode;
}

在这里插入图片描述
可以怎么写但是这里水太深你可能把握不住
在这里插入图片描述

头插结点

我们只要抓住一点把要操作的结点事先存储起来不管我们怎么连接结点我们都找的到要操作的结点

//头插
void ListPushFront(ListNode*phead, LTDataType x)
{
	 assert(phead != NULL);
	 ListNode*NewNode = CreateListNode(x);
	 ListNode*first = phead->next;
	 phead->next = NewNode;
	 NewNode->prev = phead;
	 NewNode->next = first;
	 first->prev = NewNode;
}

尾删结点

//尾删
void ListPopBack(ListNode*phead)
{
	  assert(phead != NULL);
	  assert(phead->next != phead);
	  ListNode*tail = phead->prev;
	  ListNode*prev = tail->prev;
	  
	  prev->next = phead;
	  phead->prev = prev;
	  free(tail);
	  tail = NULL;
}

在这里插入图片描述

头删结点

//头删
void ListPopFront(ListNode*phead)
{
	   assert(phead != NULL);
	   assert(phead->next != phead); 
	   ListNode*first = phead->next;//除掉头结点第一个结点
	   ListNode*second = first->next;//除掉头结点第二个结点
	   
	   phead->next = second;
	   second->prev = phead;
	   free(first);
	   first = NULL;
}

查找节点值为x的结点

查找节点值为x的结点返回指向节点的指针

//查找节点值为x返回指向节点的指针
ListNode* ListFind(ListNode*phead, LTDataType x)
{
	  ListNode*cur = phead->next;
	  while (cur != phead)
	  {
		  if (cur->data == x)
		  {
			  return cur;
		  }
		  cur = cur->next;
	  }
	  return NULL;
}

在pos前面插入一个结点

//在pos指针指向的节点前插入一个节点
void ListInsert(ListNode*pos, LTDataType x)
{
	   assert(pos != NULL);
	   ListNode*NewNode = CreateListNode(x);
	   ListNode*prev = pos->prev;
	   prev->next = NewNode;
	   NewNode->prev = prev;
	   NewNode->next = pos;
	   pos->prev = NewNode;
}

删除pos指针指向的结点

void ListErase(ListNode*pos)
{
	   assert(pos !=NULL);
	   ListNode*next = pos->next;
	   ListNode*prev = pos->prev;
	   prev->next = next;
	   next->prev = prev;
	   free(pos);
	   pos = NULL;
}

链表长度

//链表长度
int ListLength(ListNode*phead)
{
	int len = 0;
	ListNode*cur = phead->next;
	while (cur != phead)
	{
		len++;
		cur = cur->next;
	}
	return len;
}

六.总结

只要搞懂结构体指针明白链表的概念直接拿捏相信很多人学完了链表还是不知道链表会用在什么地方因为我们平时编程基本上用不到链表但是链表在操作系统中的使用非常广泛所以链表是非常重要重要的数据结构有兴趣的可以看看在实际项目中链表的应用->《FreeRTOS实时操作系统-链表的源码解析》

结束语
最近发现一款刷题神器如果大家想提升编程水平玩转C语言指针还有常见的数据结构最重要的是链表和队列后面嵌入式学习操作系统的时如freerots、RT-Thread等操作系统链表与队列知识大量使用。
大家可以点击下面连接进入牛客网刷题
点击跳转进入网站(C语言方向)
点击跳转进入网站(数据结构算法方向)

在这里插入图片描述

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：JavaScript中的原型链

下一篇：CentOS7.9配置Nginx反向代理+NodeJS部署上线

“C语言链表超详解” 的相关文章

webpack前端应用之基础打包1年前 (2023-02-02)
磨金石教育技能干货分享｜年味摄影作品选登：你的春节怎么过的1年前 (2023-02-02)
菜鸡的bug-前端开发的get请求携带对象参数的问题1年前 (2023-02-02)
React动画实现方案之 Framer Motion，让你的页面“自己”动起来1年前 (2023-02-02)
C#中的随机数_c# 随机数1年前 (2023-02-02)
【RocketMQ】消息拉模式分析1年前 (2023-02-02)
计算机网络——高效校园网络设计与实现（华为模拟器eNSP实现）_ensp综合设计word1年前 (2023-02-02)
三十一岁只是一种新的二十一岁1年前 (2023-02-02)
不用梯子，GitHub也能访问并提速1年前 (2023-02-02)
《RPC实战与核心原理》学习笔记Day131年前 (2023-02-02)

阿里云国际版