🧑‍💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

带头结点的双向循环链表

• 前言
• 一、什么是带头结点的双向循环链表？
• 二、带头结点的双向循环链表基本操作实现
• • 双链表中结点类型的描述如下：
  • 1. 动态申请一个结点
  • 2. 初始化链表
  • 3. 链表查找
  • 4. 在链表的pos位置之前插入元素
  • 5. 删除在链表的pos位置的元素
  • 6. 链表尾插
  • 7. 链表尾删
  • 8. 链表头插
  • 9. 链表头删
  • 10. 链表清空
  • 11. 链表销毁
• 三、源代码及运行结果展示
• • 1.DCHListNode.h
  • 2.DCHListNode.c
  • 3.test.c
  • 结果展示：
• 总结

前言

  上篇博客带大家认识了单链表，单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次向后遍历。对于插入、删除操作得从头遍历，尤其是在链表尾部，还有一点就是无法一步的访问到某个节点的前驱节点，也就是说访问前驱节点的时间复杂度为O(n)。为了避免这样的缺点，便引出了双向循环链表

一、什么是带头结点的双向循环链表？

  首先，它是一个链表，通过指针将所有的结点连接在一起；其次，循环链表表示整个链表从头到尾构成一个环，链表尾结点的next指针指向头结点；再者，双向表示链表结点有两个指针prev和next，分别指向其前驱结点和后继节点；最后，带头结点表示链表的第一个有效结点前附加一个结点，头结点的数值域不设任何信息。带头结点的双向循环链表如下图所示：

看似带头结点的双向循环链表的结构更为复杂，但是对于之前单链表的尾插尾删操作更为简单。

二、带头结点的双向循环链表基本操作实现

注意： 该链表带头结点，所以在进行任何的插入删除操作都无需传二级指针，因为对于头指针的指向并不会改变，只会改变链表的结点结构体本身。但是在销毁操作下，就必须传二级指针，因为销毁操作是将头结点也要删除掉，也就意味着会改变头指针的指向。

双链表中结点类型的描述如下：

typedef int DHCListNode; //每个结点的数值类型为 inttypedef struct DHCList
{DHCListNode data;struct DHCList* prev;  //前驱指针struct DHCList* next;  //后继指针
}DHCList;

1. 动态申请一个结点

DHCList* BuyDHCListNode(DHCListNode data)
{DHCList* newNode = (DHCList*)malloc(sizeof(DHCList));if (newNode == NULL){return NULL;}newNode->data = data;newNode->next = NULL; //对于没一个刚申请的结点让其前驱指针和后继指针都指向NULLnewNode->prev = NULL;return newNode;
}

2. 初始化链表

在对链表的任何操作之前得先创建一个头结点，根据双向循环的特性，需让头结点的prev和next指针都指向其自己。

DHCList* ListInit()
{DHCList* pHead = BuyDHCListNode(0);if (pHead == NULL){return NULL;}pHead->next = pHead;pHead->prev = pHead;return pHead;
}

3. 链表查找

从链表的头结点的后继结点开始逐一匹配，直到找到值相同的结点进行返回，若当查找结点一直后继到头结点时意味着没有该结点，就返回NULL

DHCList* ListFind(DHCList* pHead, DHCListNode data)
{assert(pHead);DHCList* cur = pHead->next;while (cur != pHead){if (cur->data == data){return cur;}cur = cur->next;}return NULL;
}

4. 在链表的pos位置之前插入元素

void ListInsert(DHCList* pos, DHCListNode data)
{assert(pos);DHCList* newNode = BuyDHCListNode(data);//以下四步不能混乱，如果先执行了三四步，那么就无法通过pos结点找到newnode结点的前驱结点。newNode->next = pos;newNode->prev = pos->prev;pos->prev->next = newNode;pos->prev = newNode;
}

5. 删除在链表的pos位置的元素

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

6. 链表尾插

链表的尾删可以用链表pos位置插入进行复用，因为链表的插入是在pos位置之前插入，所以在链表尾插的函数里直接将pos改为头结点即可。

void ListPushBack(DHCList* pHead, DHCListNode data)
{assert(pHead);ListInsert(pHead, data);
}

7. 链表尾删

l链表的尾删同样也可以进行复用，直接将pos改为尾结点即可，也就是头结点的前驱节点。

void ListPopBack(DHCList* pHead)
{assert(pHead);ListErase(pHead->prev); //头结点的前驱节点（链表尾结点）
}

8. 链表头插

链表头插即为将待插结点插在头结点之后。

void ListPushFront(DHCList* pHead, DHCListNode data)
{assert(pHead);ListInsert(pHead->next, data); //
}

9. 链表头删

void ListPopBack(DHCList* pHead)
{assert(pHead);ListErase(pHead->prev); //删除头结点的后继结点
}

10. 链表清空

该函数意为将链表中除头结点之外的所有结点都销毁。

void ListClear(DHCList* pHead)
{assert(pHead);DHCList* cur = pHead->next;while (cur != pHead){pHead->next = cur->next;free(cur);cur = pHead->next;}pHead->next = pHead;pHead->prev = pHead;
}

11. 链表销毁

void ListDestory(DHCList** pHead)  //参数为二级指针
{assert(pHead);ListClear(*pHead);  //先清空链表，再释放掉头节点即可。free(*pHead);*pHead = NULL;
}

三、源代码及运行结果展示

1.DCHListNode.h

结构体创建及函数声明

#include 
#include 
#include typedef int DHCListNode;typedef struct DHCList
{DHCListNode data;struct DHCList* prev;struct DHCList* next;
}DHCList;DHCList* ListInit();DHCList* BuyDHCListNode(DHCListNode data);DHCList* ListFind(DHCList* pHead, DHCListNode data);void ListPushBack(DHCList* pHead, DHCListNode data);void ListPushFront(DHCList* pHead, DHCListNode data);void ListPopBack(DHCList* pHead);void ListPopFront(DHCList* pHead);void ListInsert(DHCList* pos, DHCListNode data);void ListErase(DHCList* pos);void ListPrint(DHCList* pHead);void ListClear(DHCList* pHead);void ListDestory(DHCList** pHead);void TestList();

2.DCHListNode.c

方法实现

#include "DCHListNode.h"DHCList* BuyDHCListNode(DHCListNode data)
{DHCList* newNode = (DHCList*)malloc(sizeof(DHCList));if (newNode == NULL){return NULL;}newNode->data = data;newNode->next = NULL;newNode->prev = NULL;return newNode;
}DHCList* ListInit()
{DHCList* pHead = BuyDHCListNode(0);if (pHead == NULL){return NULL;}pHead->next = pHead;pHead->prev = pHead;return pHead;
}DHCList* ListFind(DHCList* pHead, DHCListNode data)
{assert(pHead);DHCList* cur = pHead->next;while (cur != pHead){if (cur->data == data){return cur;}cur = cur->next;}return NULL;
}void ListPushBack(DHCList* pHead, DHCListNode data)
{assert(pHead);ListInsert(pHead, data);
}void ListPushFront(DHCList* pHead, DHCListNode data)
{assert(pHead);ListInsert(pHead->next, data);
}void ListPopBack(DHCList* pHead)
{assert(pHead);ListErase(pHead->prev);
}void ListPopFront(DHCList* pHead)
{assert(pHead);ListErase(pHead->next);
}//在pos之前插入
void ListInsert(DHCList* pos, DHCListNode data)
{assert(pos);DHCList* newNode = BuyDHCListNode(data);newNode->next = pos;newNode->prev = pos->prev;pos->prev->next = newNode;pos->prev = newNode;
}void ListErase(DHCList* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}void ListPrint(DHCList* pHead)
{assert(pHead);DHCList* cur = pHead->next;while (cur != pHead){printf("%d----", cur->data);cur = cur->next;}printf("NULL\n");
}void ListClear(DHCList* pHead)
{assert(pHead);DHCList* cur = pHead->next;while (cur != pHead){pHead->next = cur->next;free(cur);cur = pHead->next;}pHead->next = pHead;pHead->prev = pHead;
}void ListDestory(DHCList** pHead)
{assert(pHead);ListClear(*pHead);free(*pHead);*pHead = NULL;
}void TestList()
{DHCList* pHead = ListInit();ListPushBack(pHead, 1);ListPushBack(pHead, 2);ListPushBack(pHead, 3);ListPushBack(pHead, 4);ListPrint(pHead);ListPushFront(pHead, 0);ListPrint(pHead);ListPopFront(pHead);ListPrint(pHead);ListPopBack(pHead);ListPrint(pHead);ListClear(pHead);ListPrint(pHead);ListDestory(&pHead);//ListPrint(pHead);
}

3.test.c

主函数

#include "DCHListNode.h"int main()
{TestList();return 0;
}

结果展示：

总结

  带头结点的双向循环链表的结构比较复杂，所以对链表进行插入删除操作时一定要注意指针指向的先后顺序；还有就是传递的参数为一级指针即可，只有在删除链表时才需传二级指针。
  文章若有不足的地方还请大佬指正！！！