网站导航
> 文档中心 > 【玩转链表③】碾压单链表之双向带头循环链表

【玩转链表③】碾压单链表之双向带头循环链表

网友: 文档中心 2022-03-28 20:19:00

学习导航

      • 一、前言
      • 二、双向带头循环链表基本介绍
        • ①双向的体现
        • ②循环的体现
        • ③带头的体现
      • 三、双向带头循环链表接口实现
        • ①准备函数
        • ②头插尾插函数接口
        • ③头删尾删函数接口
        • ④查找函数接口
        • ⑤指定位置插入和删除接口
        • ⑥链表清空函数
      • 四、与顺序表的比较

一、前言

🐱‍💻博主概况:  霉霉铁杆粉、算法爱好者、南邮大一学生
🐱‍👤推荐资料: 《代码随想录》在线资源
🐱‍💻适和对象：C语言玩家 + 链表初学者
🐱‍🚀专栏宣传：算法入门系列长期更新，欢迎点赞收藏，祝大家学有所获。

【⭐核心知识点】

  • 双向带头循环链表的接口实现
  • 双向带头循环链表的优缺点 VS 顺序表的优缺点

二、双向带头循环链表基本介绍

①双向的体现

typedef struct List{int val;struct List* prev;struct List* next;}List;

🌮【比较】：和单链表相比，双向带头循环链表不仅能指向下一个结点还能指向前一个结点。
🥪【碾压①】：单链表只适合向后插入或删除，否则要从头开始遍历找到前一个结点。而双向链表找到前一个结点是不费吹灰之力的。

②循环的体现

总而言之就是各个结点之间头尾相连串联成一个环 在这里插入图片描述
🥪【碾压②】：单链表找到尾结点必须要从头到尾进行遍历。而双向循环链表通过头结点就可以直接访问到尾结点。

③带头的体现

带的这个头就是哨兵结点
在这里插入图片描述
🌮【作用】：哨兵结点不存储任何有效数据。关于哨兵结点详细的优点和作用大家可以参考这篇博客【玩转链表②】没做过这几道题目，别再敢说单链表入门了

三、双向带头循环链表接口实现

①准备函数

List* ListInit() //创建哨兵结点{List* phead = (List*)malloc(sizeof(List));phead->next = phead;phead->prev = phead;return phead;}void ListPrint(List* phead){List* cur = phead->next;while (cur != phead){printf("%d ", cur->val);cur = cur->next;}}

在这里大家也看到了，双向循环链表该怎么初始化
在这里插入图片描述

②头插尾插函数接口

//尾插函数void ListPushBack(List* phead, int val){assert(phead);List* newNode = (List*)malloc(sizeof(List));newNode->val = val;//(1)newNode->prev = phead->prev;phead->prev->next = newNode;//(2)newNode->next = phead;phead->prev = newNode;}

【思考①】：prev还是next，傻傻分不清怎么办？🥪
【答①】: 首先确定一种绕行方向。如下图中我们将顺时针方法规定为next的方向，那么只要箭头反向是顺时针的我们不用多想就可以判断为next指针。是不是很简单呢？
在这里插入图片描述

【思考②】：上述代码中语句(1)和语句(2)可以互换顺序吗？🥪
【答②】不可以。这样就不能通过头结点直接找到尾结点。
 
【思考③】 有没有不用思考先后顺序的办法？
【答③】解决的办法也很简单，实现将需要用到的结点保存下来即可。在头插中我们可以看到范例：

void ListPushFront(List* phead, int val){List* newNode = (List*)malloc(sizeof(List));newNode->val = val;List* next = phead->next; //将需要用到的结点保存下来。newNode->prev = phead;phead->next = newNode;newNode->next = next;next->prev = newNode;}

③头删尾删函数接口

void ListPopFront(List* phead){assert(phead);List* next = phead->next->next;free(phead->next);phead->next = next;next->prev = phead;}void ListPopBack(List* phead){assert(phead);List* prev = phead->prev->prev;free(phead->prev);phead->prev = prev;prev->next = phead;}

 有了单链表的学习经验【玩转链表①】单链表动图图解（超详解），上述代码的实现是不是异常的轻松呢？

④查找函数接口

List* ListFind(List* phead, int val){assert(phead);List* cur = phead->next;while (cur != phead){if (cur->val == val)return cur;cur = cur->next;}return NULL;}

【作用🥪】：查找函数寻找并返回链表中值为val的结点地址。与之后的Insert()函数和Erase()函数配合使用，实现在指定位置插入删除的效果。

⑤指定位置插入和删除接口

void ListInsert(List* pos, int val) //在pos位置插入{assert(pos);List* newNode = (List*)malloc(sizeof(List));List* prev = pos->prev;newNode->val = val;newNode->prev = prev;prev->next = newNode;newNode->next = pos;pos->prev = newNode;}void ListErase(List* pos) //将pos位置的结点删除{assert(pos);List* next = pos->next;List* prev = pos->prev;free(pos);next->prev = prev;prev->next = next;}

⑥链表清空函数

void ListDestroy(List* phead){assert(phead);List* cur = phead->next;while (cur != phead){List* next = cur->next;free(cur);cur = next;}free(phead);}

【思考④】我们free一个空间后为了避免“野指针”后都顺带将结点置为NULL，这里需要对phead结点置空吗?
【答④】不能改也没必要改。由于phead只是实参的临时拷贝，修改phead对实参没影响，所以说不能该。
 如果要修改我们就需要传入二级指针，但这样就会影响接口的统一性。联想free函数，为什么函数设计者不直接将将指针置空呢？我想也是为了保证接口的统一性。

四、与顺序表的比较

①顺序表【玩转链表③】碾压单链表之双向带头循环链表
优点：

  1. 由于数学表物理空间上是连续的。方便用于下标的随机访问。因此排序算法、二分算法等算法中，顺序表占有绝对的优势。
  2. CPU高速缓存命中率会更高

缺点：

  1. 由于物理空间是连续的，空间不过需要扩容。但是扩容的大小不好把握。扩容小了重复扩容则效率低下，扩容大了则容易造成空间浪费。
  2. 头部或者中间部位进行插入删除会挪动之后的数据，效率低下，为O(N)

解释：
 大家可能对顺序表的优点②可能不太了解，这里做单独的说明。会涉及点CPU缓存知识的知识，但面试的时候能回答出来就是加分项：
在这里插入图片描述
 由于CPU的处理速度大于内存加载数据的速度，因此CPU并不直接从内存中读取，而是要将数据和指令加载到三级缓存和寄存器中去，他们的加载速度远快于内存。
 CPU在加载的时候不是一个字节一个字节的加载，而是一块一块的加载。根据局部性原理，CPU很有可能会访问到当前位置之后的数据，所以实现也将他们加载到三级缓存和寄存器中去。
 所以顺序表在内存中连续存储的优势就可以提高高速缓存命中率，加快读取的速度。

②双向带头循环链表
在这里插入图片描述
优点：

  1. 任意位置插如数据效率高O(1)
  2. 可以按需申请和释放空间

缺点：

  1. 不支持下标的随机访问。
网络标签：

相关问题