1.前言
💓博主CSDN:杭电码农-NEO💓🎉🎉🎉
⏩专栏分类:数据结构学习分享(持续更新中🫵)⏪🎉🎉🎉
我们上一期说到,两链表中有两个最常用的结构,一个是最简单的无头不循环单向链表,还有一个就是 结构相对比较复杂的带头双向循环链表 ,我们这一章节就来分享双向带头循环链表的具体实现:
要看所有代码的朋友: 💯 我的码云放在了最后 💯
2. 结构分析
与我们上一章讲的单链表不同,这里双向带头循环链表的结构要复杂一点,主要需要注意这几个点:
定义结构体时,单链表只需要定义一个指针next,双链表需要定义额外一个指针:prev用来指向上一个节点
带头(带哨兵位)的链表在初始化时就要给哨兵位开辟一份空间,并且哨兵位不存储数据,第一个节点要链接在哨兵位的下一个位置
循环的链表的尾节点的next不能指向NULL,要指向第一个节点,形成循环结构
我们在进行插入删除的时候可以不传二级指针!因为我们拥有了哨兵位作为我们指针指向的第一个位置,并且哨兵位是不会改变的!
不循环的链表判断尾节点是cur->next == NULL时,然而循环的带头链表判断尾节点是cur->next==head时,这里的head指的是哨兵位
3. 双链表的实现
单链表我们使用的名字是SList,意为single list 就是单个的意思,这里我们直接用List表示双链表
3.1 初始化结构
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<malloc.h> typedef int LTDateType;//随时可以改变类型 typedef struct ListNode { LTDateType data; struct ListNode* prev;//指向上一个节点 struct ListNode* next;//指向下一个节点 }LTNode;//简化名字
3.2 初始化函数
在我们写初始化函数之前我们要先明白一点,那就是当链表为空时,我们哨兵位的next和prev都指向自己本身!
LTNode* ListInit() { LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//为哨兵位开辟一个节点 phead->next = phead; phead->prev = phead; return phead;//将phead返回后,在test.c文件中赋值给结构体指针 }
void TestList1() { LTNode* plist = ListInit();//plist里面存储一个哨兵位 }
3.3 尾插函数
我们说存储数据的结构都离不开增删查改,这里我们定义的双向带头循环链表进行增删查改是很简单的
void ListPushBack(LTNode* phead, LTDateType x)//尾插 { assert(phead); LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//为插入的数据开辟空间 if (newnode == NULL)//这个if语句是为了判断我们的动态开辟空间有没有失败 { printf("fail"); exit(-1); } newnode->data = x;//将数据x给上 LTNode* tail = phead->prev;//这里也可以不定义tail,直接用phead->prev表示尾 tail->next = newnode;//尾节点与新节点相连 newnode->prev = tail;//新的尾节点的prev与旧的尾相连 newnode->next = phead;//新的尾节点与头相连形成循环 phead->prev = newnode; }
我们发现当我们定义链表结构为双向带头循环链表时,插入数据是很方便的,只需要判断好链接关系就可以了,而我们之前的单链表还需要判断链表为空的情况,这种情况要拿出来特殊处理,但是这个地方当链表为空时也是没有问题的!
3.4 尾删函数
我们有了之前的基础后,直接上代码!
void ListPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);//不能把哨兵为给删除了 LTNode* tail = phead->prev; LTNode* prev = tail->prev;//后面就处理链接关系 free(tail); tail = NULL; prev->next = phead; phead->prev = prev; }
值得注意的是,这里的assert(phead->next!=phead)是当我们的phead->next等于自己本身时,代表我们链表中已经没有数据了,只剩下一个哨兵位了.这时需要断言报错 👍👍👍
3.5 头插函数
void ListPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//只要是插入数据就需要开辟空间 newnode->data = x; LTNode* next = phead->next;//头插相当于就是插入在哨兵位后面 phead->next = newnode;//注意链接关系别写漏就没问题 newnode->prev = phead; newnode->next = next; next->prev = newnode; }
同样的,当我们链表中没有数据时,这时的头插也是没有问题的,这里我就不做过多说明
3.6 头删函数
void ListPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTNode* next = phead->next; phead->next = next->next; next->next->prev = phead; free(next); next = NULL; }
头删和尾删一样,不能把哨兵位一起删了,并且需要注意一点,我们的free不能太早使用,不然我们就找不到我们next的next和next的prev了,所以我们要把所有链接关系全部修改完之后,才能把next的空间给释放掉
3.7 销毁链表
void ListDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur!=phead)//释放掉所有的数据空间 { LTNode* next = cur->next;//这里需要定义一个next指针,因为我们把cur给释放掉后就找不到cur->next的了 free(cur); cur = next; } free(phead);//最后将哨兵位也释放掉,然后置空 phead = NULL; }
3.8 其他函数
这里我给出几个除了头插头删,尾插尾删的函数.
Find函数:返回与x值相同的节点
LTNode* ListFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while ( cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
Insert函数:在pos位置之前插入数据
void ListInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); newnode->data = x; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; prev->next = newnode; }
Erase函数:删除pos位置的节点
void ListErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
. 缓存利用率
我们上一章总结顺序表和链表的区别的时候提到:顺序表的缓存利用率高,链表的缓存利用率低,那么到底什么是缓存利用率?这里我给大家大致提一下:我们的计算器存在很多存储方式:
我们在数组中开辟空间和在链表上开辟空间时,这种缓存的命中是不一样的,有兴趣了解的朋友具体的细节可以参考这篇文章CPU缓存知识.
5. 总结
我们关于链表的知识的分享就要告一段落了,但是链表这一章节虽然只有两次分享,但是它在诸多面试题中考察的概率是很高的,特别是单链表,因为我们知道单链表是有很多缺陷的,所以在校招和很多OJ题中,单链表考察的地方非常之多,建议多刷刷题找找思路,我的专栏单链表OJ中也总结了不少OJ题的思路以及衍生问题,有兴趣的朋友可以来指导指导.
