【数据结构】带头双向循环链表—C语言版（单链表我们分手吧，不要再找我玩了！！！）

文章目录

• 一、前言
• 二、链表的分类
• • 1. 单向或者双向链表
  • 2. 带头或者不带头链表
  • 3. 循环或者非循环
  • 4. 最常用链表
• 三、带头双向循环链表详解
• • 创建带头双向循环链表
  • ⭕接口1：定义结构体（LTNode）
  • ⭕接口2：初始化（创建哨兵卫）（LTInit）
  • ⭕接口3：打印（LTPrint）
  • ⭕接口4：创建新结点（BuyLTNode）
  • ⭕接口5：释放（LTDestroy）
  • ⭕接口6：判空（LTEmpty）
  • ⭕接口7：头插（LTPushFront）
  • ⭕接口8：尾插（LTPushBack）
  • ⭕接口9：头删（LTPopFront）
  • ⭕接口10：尾删（LTPopBack）
  • ⭕接口11：查找（LTFind）
  • ⭕接口12：修改（LTModify）
  • ⭕接口13：在pos之前插入（LTInsert）
  • ⭕接口14：删除pos位置的值（LTErase）
• 四、完整代码
• • List.h
  • List.c
  • Test.c

一、前言

在前面我们学习实现了单链表（无头单向不循环链表），这里我们引入带头双向循环链表
很明显这两种链表的结构截然不同，但都是作为链表最常使用链表结构
前者因其结构上的缺点而作为面试考题的常驻嘉宾，而且复杂麻烦
后者则是以结构最优著称，实现起来也是非常的简单（少了单链表头节点，尾节点，前一节点等问题的困扰），可以说是最屌的链表结构

二、链表的分类

1. 单向或者双向链表

• 单向：节点结构中只存在下一节点的地址，所以难以从后一节点找到前一节点
• 双向：节点结构中存在前一节点和后一节点的地址，寻找前一节点和后一节点很便利

2. 带头或者不带头链表

• 带头：在本来的头节点之前还有一个哨兵卫节点作为头节点，它的址域指针指向头节点，值域不做使用
• 不带头：没有哨兵卫头节点，在尾删尾插等问题中要考虑头节点的情况（局限）

3. 循环或者非循环

• 循环：头节点会与尾节点相连
• 非循环：头节点不与尾节点相连

4. 最常用链表

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
无头单向非循环链表

带头双向循环链表

• 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
• 2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

三、带头双向循环链表详解

创建带头双向循环链表

这里先创建三个文件：
1️⃣：List.h文件，用于函数的声明
2️⃣：List.c文件，用于函数的定义
3️⃣：Test.c文件，用于测试函数
建立三个文件的目的： 将链表作为一个项目来进行编写，方便我们的学习与观察。

⭕接口1：定义结构体（LTNode）

请看代码与注释

//自定义类型typedef int ListNodeDataType;//创建双向链表typedef struct ListNode{struct ListNode* prev; //前址域struct ListNode* next; //后址域ListNodeDataType data; //值域}LTNode;

⭕接口2：初始化（创建哨兵卫）（LTInit）

请看代码与注释

//初始化（创建哨兵卫）LTNode* LTInit(){LTNode* phead = BuyLTNode(-1); //哨兵卫不存储有效值phead->prev = phead; //初始化哨兵卫头节点址域phead->next = phead;return phead;}

⭕接口3：打印（LTPrint）

请看代码与注释

//打印void LTPrint(LTNode* phead){//断言传入指针不为NULLassert(phead);printf("guard");LTNode* cur = phead->next;while (cur != phead){printf("%d", cur->data); //打印数据cur = cur->next; //找到下一个节点}printf("\n");}

⭕接口4：创建新结点（BuyLTNode）

请看代码与注释

//创建新节点LTNode* BuyLTNode(ListNodeDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail"); //失败打印错误信息并结束进程return;}//初始化节点newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;}

⭕接口5：释放（LTDestroy）

请看代码与注释

//释放void LTDestroy(LTNode* phead){//断言传入指针不为NULLassert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next; //记录下一个节点地址free(cur); //释放当前节点cur = next; //找到下一个节点}free(phead);}

⭕接口6：判空（LTEmpty）

请看代码与注释

//判空bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead; //判断只剩哨兵卫头结点的情况}

⭕接口7：头插（LTPushFront）

请看代码与注释

//头插void LTPushFront(LTNode* phead, ListNodeDataType x){assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next; //记录哨兵卫头结点的下一节点//构建各节点之间的关系phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

⭕接口8：尾插（LTPushBack）

请看代码与注释

//尾插void LTPushBack(LTNode* phead, ListNodeDataType x){assert(phead);LTNode* tail = phead->prev; //找到尾节点LTNode* newnode = BuyLTNode(x);//构建尾节点与新节点，新节点与哨兵卫头结点的关系tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

⭕接口9：头删（LTPopFront）

请看代码与注释

//头删void LTPopFront(LTNode* phead){assert(!LTEmpty(phead));LTNode* first = phead->next; //记录哨兵卫头节点下一节点及其的下一节点LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);}

⭕接口10：尾删（LTPopBack）

请看代码与注释

//尾删void LTPopBack(LTNode* phead){//判空 以及 判断只剩哨兵卫头结点的情况assert(!LTEmpty(phead));//记录尾节点及其前一节点LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;//构建尾节点前一节点与哨兵卫头结点的关系tailPrev->next = phead;phead->prev = tailPrev;free(tail); //释放尾节点}

⭕接口11：查找（LTFind）

请看代码与注释

LTNode* LTFind(LTNode* phead, ListNodeDataType x){assert(phead);LTNode* cur = phead->next;;while (cur != phead){if (cur->data == x) //比较数据{return cur;}cur = cur->next; //找到下一个节点}return NULL; //没找到则返回NULL}

⭕接口12：修改（LTModify）

请看代码与注释

//修改void LTModify(LTNode* phead, LTNode* pos, ListNodeDataType x){assert(phead);assert(pos);pos->data = x;}

⭕接口13：在pos之前插入（LTInsert）

请看代码与注释

//在pos之前插入void LTInsert(LTNode* pos, ListNodeDataType x){assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}

⭕接口14：删除pos位置的值（LTErase）

请看代码与注释

//删除pos位置的值void LTErase(LTNode* pos){assert(pos);//记录pos的前一节点和后一节点LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos); //释放节点}

四、完整代码

List.h

#pragma once#include#include#include#include//自定义类型typedef int ListNodeDataType;//创建双向链表typedef struct ListNode{struct ListNode* prev;struct ListNode* next;ListNodeDataType data;}LTNode;//初始化（创建哨兵卫）LTNode* LTInit();//打印void LTPrint(LTNode* phead);//释放void LTDestroy(LTNode* phead);//判空bool LTEmpty(LTNode* phead);//头插void LTPushFront(LTNode* phead, ListNodeDataType x);//尾插void LTPushBack(LTNode* phead, ListNodeDataType x);//头删void LTPopFront(LTNode* phead);//尾删void LTPopBack(LTNode* phead);//查找LTNode* LTFind(LTNode* phead, ListNodeDataType x);//修改void LTModify(LTNode* phead, LTNode* pos, ListNodeDataType x);//在pos之前插入void LTInsert(LTNode* pos, ListNodeDataType x);//删除pos位置的值void LTErase(LTNode* pos);

List.c

#include "List.h"//创建新节点LTNode* BuyLTNode(ListNodeDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;}//初始化（创建哨兵卫）LTNode* LTInit(){LTNode* phead = BuyLTNode(-1); //哨兵卫不存储有效值phead->prev = phead;phead->next = phead;return phead;}//打印void LTPrint(LTNode* phead){assert(phead);printf("guard");LTNode* cur = phead->next;while (cur != phead){printf("%d", cur->data);cur = cur->next;}printf("\n");}//释放void LTDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}//判空bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;}//头插void LTPushFront(LTNode* phead, ListNodeDataType x){assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}头插//void LTPushFront(LTNode* phead, ListNodeDataType x)//{//assert(phead);////LTInsert(phead->next, x);//}//尾插void LTPushBack(LTNode* phead, ListNodeDataType x){assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}尾插//void LTPushBack(LTNode* phead, ListNodeDataType x)//{//assert(phead);////LTInsert(phead, x);//}//头删void LTPopFront(LTNode* phead){assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);}头删//void LTPopFront(LTNode* phead)//{//assert(!LTEmpty(phead));////LTEmpty(phead->next);//}//尾删void LTPopBack(LTNode* phead){assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;free(tail);}尾删//void LTPopBack(LTNode* phead)//{//assert(!LTEmpty(phead));////LTEmpty(phead->prev);//}//查找LTNode* LTFind(LTNode* phead, ListNodeDataType x){assert(phead);LTNode* cur = phead->next;;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}//修改void LTModify(LTNode* phead, LTNode* pos, ListNodeDataType x){assert(phead);assert(pos);pos->data = x;}//在pos之前插入void LTInsert(LTNode* pos, ListNodeDataType x){assert(pos);LTNode* prev = pos->prev;LTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}//删除pos位置的值void LTErase(LTNode* pos){assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);}

Test.c

#include "List.h"//头插测试void TestList01(){LTNode* plist = LTInit();LTPushFront(plist, 4);LTPushFront(plist, 3);LTPushFront(plist, 2);LTPushFront(plist, 1);LTPrint(plist);LTDestroy(plist);plist = NULL;}//尾插测试void TestList02(){LTNode* plist = LTInit();LTPushBack(plist, 4);LTPushBack(plist, 3);LTPushBack(plist, 2);LTPushBack(plist, 1);LTPrint(plist);LTDestroy(plist);plist = NULL;}//头删测试void TestList03(){LTNode* plist = LTInit();LTPushFront(plist, 4);LTPushFront(plist, 3);LTPushFront(plist, 2);LTPushFront(plist, 1);LTPopFront(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;}//尾删测试void TestList04(){LTNode* plist = LTInit();LTPushFront(plist, 4);LTPushFront(plist, 3);LTPushFront(plist, 2);LTPushFront(plist, 1);LTPopBack(plist);LTPrint(plist);LTDestroy(plist);plist = NULL;}//查找修改测试void TestList05(){LTNode* plist = LTInit();LTPushFront(plist, 4);LTPushFront(plist, 3);LTPushFront(plist, 2);LTPushFront(plist, 1);LTNode* pos = LTFind(plist, 3);if (pos){LTModify(plist, pos, 8);}LTPrint(plist);LTDestroy(plist);plist = NULL;}//在pos之前插入void TestList06(){LTNode* plist = LTInit();LTPushFront(plist, 4);LTPushFront(plist, 3);LTPushFront(plist, 2);LTPushFront(plist, 1);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 7);}LTPrint(plist);LTDestroy(plist);plist = NULL;}//删除pos位置的值void TestList07(){LTNode* plist = LTInit();LTPushFront(plist, 4);LTPushFront(plist, 3);LTPushFront(plist, 2);LTPushFront(plist, 1);LTNode* pos = LTFind(plist, 2);if (pos){LTErase(pos);}LTPrint(plist);LTDestroy(plist);plist = NULL;}int main(){//TestList01();//TestList02();//TestList03();//TestList04();//TestList05();//TestList06();//TestList07();return 0;}

这期内容比较容易一些而且比较有趣，希望烙铁们可以理解消化哦！

总结
以上就是 【数据结构】带头双向循环链表—C语言版 的全部内容啦
本文章所在【数据结构与算法】专栏，感兴趣的烙铁可以订阅本专栏哦
前途很远，也很暗，但是不要怕，不怕的人面前才有路。
小的会继续学习，继续努力带来更好的作品
创作写文不易，还多请各位大佬uu们多多支持哦