【数据结构】带头双向循环链表(上)

简介: 【数据结构】带头双向循环链表

😎前言


前面学习了单链表的结构,并且做了些许单链表的OJ练习,相信大家已经对单链表的结构了如指掌。因此,本章带来了与单链表同源的但拥有不同的结构的链表 — 带头双向循环链表供大家学习。


可能大家听到带头双向循环链表这个名字,就会认为该结构很复杂(的确很复杂,是链表当中结构最复杂的),肯定比单链表要难许多,说实在的,如果没有前面单链表的铺垫,直接上这个结构,那肯定挺难的。但现在我们有了单链表的基础,并且做了挺多单链表的题了,也就不用怕了。


实际上,带头双向循环链表只是 看起来难,听起来难,但它实现起来,比单链表简单多了。并且许多细节地方都不需要那么的繁琐。


注意:下面所说的头节点都是指那个哨兵位的头节点。


带头双向循环链表的初始化


既然是双向,也就是即指向前也指向后,因此每一个节点不光要存储一个数据,还要两个结构体指针,一个指针prev指向前,一个指针next指向后,也就是next指针指向下一个节点,prev指针指向前一个节点。按照这个形式由一个一个的节点组成的链表,就是双向的,这剔除了单链表的单向性。由此可知遍历这个双向链表不仅可以往后遍历,还可以往前遍历,这是不是方便了许多呢?


那循环在这是什么意思?循环就是链表的第一个节点的prev指向链表的最后一个节点,链表的最后一个节点的next指向链表的第一个节点,例如:


不带哨兵位的头节点的双向循环链表:


086cb61de9bd406c90f22dc1a5b31a06.png

但是这里,我们讨论带头的双向循环链表。


为啥要带头呢?很简单,便于下面的一系列操作。想一下,如果没有哨兵位的头节点进行增删查改,遇到头删或者头插的话,此时需要更新一下头节点,既然要更新一下头节点,那就与单链表章节一样,需要用到二级指针,或者带返回值,这就很麻烦了。但如果带哨兵位头节点的话,二级指针和返回值都不需要用到,并且头删头插尾插尾删都特别的方便,它的优势处,下面会一一体现。


带头双向循环链表:


04b198f2cbcc41c49c5500cd43f95832.png


  • 当然,有了前面的数据结构的学习,毫无疑问,这里也是需要三个文件来实现的,这里就不多说了,分别是DList.h,DList.c,test.c
  • 有了上面的介绍,我们首先包含需要用到的头文件:
#include <stdio.h>
// assert断言
#include <assert.h>
// 动态内存函数所需
#include <stdlib.h>
// 判空所需 bool 类型
#include <stdbool.h>


  • 然后将节点的结构创建出来(两个指针一个数据):
// 存储的数据的类型
typedef int LTDataType;
typedef struct ListNode
{
  // 存储数据
  LTDataType _data;
  // 指向下一个节点的指针
  struct ListNode* _next;
  // 指向前一个节点的指针
  struct ListNode* _prev;
}ListNode;  // 重命名是为了方便


  • 接着就是对各个函数接口一一实现了。各个函数接口的声明:(由于前面的与函数接口声明都在.h文件,并且该文件只有这些,这里就直接放.h文件了):
#include <stdio.h>
// assert断言
#include <assert.h>
// 动态内存函数所需
#include <stdlib.h>
// 判空所需 bool 类型
#include <stdbool.h>
// 带头+双向+循环链表增删查改实现
// 存储的数据的类型
typedef int LTDataType;
typedef struct ListNode
{
  // 存储数据
  LTDataType _data;
  // 指向下一个节点的指针
  struct ListNode* _next;
  // 指向前一个节点的指针
  struct ListNode* _prev;
}ListNode;  // 重命名是为了方便
// 创建返回链表的头结点.
ListNode* ListCreate();
// 得到一个结点
ListNode* BuyListNode(LTDataType x);
// 双向链表清理
void ListClear(ListNode* phead);
// 双向链表销毁
void ListDestory(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 判空
bool ListEmpty(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 修改某一节点的数据
void ListModify(ListNode* pos, LTDataType x);



创造一个哨兵位头节点


  • 我们首先得创造一个带哨兵位的头节点,这样才能进行后续的操作。
  • 当然,我们每次创造的一个节点都是使用malloc向内存申请一段空间来存储。
  • 这里也是一样,我们向内存申请一个节点的空间后,将这个节点的两个指针都指向自己,并且里面的数据任意给(这里不做要求,也可以不给,它默认随机值,不过最好给-1),这样就得到一个哨兵位的头节点。有了该函数的功能,我们每次测试的时候,开始都要有这一步操作:


ListNode* plist = ListCreate();  // 将plist指向那个哨兵位头节点

下面是相关接口函数功能实现:

// 创建返回链表的头结点.
ListNode* ListCreate()
{
  // BuyListNode(),该函数是获取一个节点,下面有介绍,大概理解这样操作就欧克啦
  ListNode* head = BuyListNode(-1);
  return head;
}


得到节点


该函数在获取头节点函数和所有插入函数中都需要用到,因此这里把它抽离出来单独形成一个接口,以此来提高效率。


得到一个节点,那当然是在内存中申请一段空间,这个空间就作为新的那个节点的空间。


每次得到的这个节点,让它的两个指针都先指向自己,然后数据存放自己给出的值,之后将这个节点的地址返回即可,因为该节点的空间是在堆上的,函数栈帧销毁不会影响这段空间。


下面是相关接口函数功能实现:

// 得到一个结点
ListNode* BuyListNode(LTDataType x)
{
  // 向内存中申请一个节点的空间
  ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  // 判断一下是否申请失败
  assert(newnode);
  // 将next和prev都指向自己
  newnode->_next = newnode;
  newnode->_prev = newnode;
  // 存放自己给的数据
  newnode->_data = x;
  // 返回这个节点的地址
  return newnode;
}



链表清理


  • 当我们创建了一个带头双向循环链表后,不想要了但又还想继续操作怎么办👻?当然是将每个节点释放(free)。


  • 注意:清理是将每个有效的节点删除(释放),不会干掉头节点,因此,我们从头节点的下一个节点开始,向右遍历链表,一边遍历一边删除(所以这里需要创建一个节点指针来存放下一个节点的地址),直到最后遍历到头节点的时候结束操作。


下面是相关接口函数功能实现:

void ListClear(ListNode* phead)
{
  // 避免传NULL的情况,phead是NULL就不能操作了
  assert(phead);
  // 从phead的下一个节点开始操作
  ListNode* cur = phead->_next;
  while (cur != phead)
  {
    // 存放当前节点的下一个节点的地址
    ListNode* next = cur->_next;
    free(cur);
    cur = next;
  }
}


链表销毁


我们在一系列操作后,一定要记得链表销毁,不然会出现内存泄漏的情况,尽管现在的编译器大部分都很明智了,会自动把申请的空间返还给操作系统。但是我们要养成这样一个好习惯,因此这里将该函数接口的实现放在前面。


销毁与清理可就不一样了,销毁是要将所有申请的空间释放,因此也就包括那个哨兵位的头节点。


前面已经实现了清理的函数,所以这里直接考虑复用清理的函数,最后再将头节点释放即可。


下面是相关接口函数功能实现:

// 双向链表销毁
void ListDestory(ListNode* phead)
{
  // 判断phead是否是NULL
  assert(phead);
  // 复用
  ListClear(phead);
  // 最后释放头节点
  free(phead);
}


打印链表


  • 打印功能可以说必不可少,它在你进行操作的时候,可以直观的展现你进行了那些操作。
  • 当然打印不需要打印头节点,你可以把头节点当作一个虚的。
  • 因此这里需要从头节点的下一个节点开始依次打印,直到遍历链表遍历到头节点时结束打印。

下面是相关接口函数功能实现:

// 双向链表打印
void ListPrint(ListNode* phead)
{
  assert(phead);
  // 从头节点的下一个开始
  ListNode* cur = phead->_next;
  // 遍历到头结束
  while (cur != phead)
  {
    // 打印当前节点的数据
    printf("%d ", cur->_data);
    // 寻找下一个节点
    cur = cur->_next;
  }
  printf("\n");
}


链表判空


  • 这里还提供一个判空函数,这个判空是判断除头节点以外还有没有其它节点,如果没有,说明空,返回true;如果有,说明不空,返回false
  • 如何来判?在前面初始化创建一个头节点时,将该节点的两个指针分别指向了自己,因此,当链表为空,没有其它节点的时候我们直接判断头节点的next或者prev指针是否指向自己就好,如果是指向自己,说明为空,反之,不为空。
  • 当在删除链表的节点的时候,判空会起到有效的作用。


下面是相关接口函数功能实现:

// 判空
bool ListEmpty(ListNode* phead)
{
  assert(phead);
  // 判断头节点的next是否指向自己,判断prev也是可行的
  return phead->_next == phead;
}


链表尾插


  • 链表的尾插,就是在链表的最后一个节点的后面连接一个节点,因此我们先要得到一个节点,然后找到链表的最后一个节点,再进行连接。
  • 由于该链表是带头双向循环链表,既然是循环,要找到最后一个节点,那可是易如反掌。它不就是头节点的prev嘛。
  • 连接过程也是简简单单:


7901277836924a08afae1130f9799b48.gif


  • 如果此时链表中没有有效的节点,那么此时直接得到一个节点与头节点连接即可,不需要考虑单链表章节是否要更新头指针的情况,这也体现了带头的优处。


下面是相关接口函数功能实现:


// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);
  // 得到一个节点
  ListNode* newnode = BuyListNode(x);
  // 存储最后一个节点的指针
  ListNode* cur = phead->_prev;
  // 连接
  cur->_next = newnode;
  newnode->_prev = cur;
  newnode->_next = phead;
  phead->_prev = newnode;
}


相关文章
|
6天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
55 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
26 3
|
2月前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
18 0
数据结构与算法学习五:双链表的增、删、改、查
|
29天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
42 0
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
2月前
|
存储 Java
【数据结构】链表
【数据结构】链表
18 1