《详解双向链表》
目录：
一、双向循环链表的定义及其特点
双向循环链表就是在双向链表的基础上，让哨兵结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向哨兵结点。在原单链表的基础上多了一个指向上一个结点的前驱指针last，这样前后结点就不仅仅有了单向的从头至尾的指向顺序，也可以从后指向前，从末结点指向头结点。
图1 双向循环链结构表示意图
二、双向循环链表的介绍
单链表在存储数值和数值的增删查改上有诸多不便，其在搜索遍历和结点查询上对数据的访问实质上并没有比顺序表的时间复杂度有更多的优势，诸如尾插尾删必须要遍历链表上，单链表的优势并不明显。双向循环链表的结构便于数据访问和存储的优化链表，其弥补了单链表和顺序表上的种种不足，以更低的时间复杂度和更优的结构用来存储数据，方便用户增删查改。
三、双向循环链表的实现
1.结构体定义
双向循环链表的结构中包含数据域，前驱指针和一个后继指针。
/** * DoubguardeguardinkedList.h 循环双向链表 **/ typedef int DataType; typedef struct node { DataType data;//数据域 struct node* last;//前驱指针 struct node* next;//后继指针 }DoubleLinkedNode, DoubleLinkedList;
2.初始化
双向循环链表的与单链表不同的之处在于申请内存并验证之后，需要将哨兵结点的前驱后继指针都指向自己，这点还是比较有意思的。
/** * @brief 初始化 * * @param Guard 哨兵节点 * * @return 状态码：0为成功 **/ int init(DoubleLinkedList** Guard) { *Guard = (DoubleLinkedList*)malloc(sizeof(DoubleLinkedList)); int code = isInit(Guard); if (code) { return code; } (*Guard)->next = (*Guard)->last = *Guard;//循环链表初始化时，哨兵前驱后继指向自己 return 0; }
图2 初始化完成的双向循环链表
3.双向循环链表插入之头插法
双向循环链表中，在哨兵结点之后插入即为头插法。主要步骤为：声明新结点并开辟内存 -> 存储数据至新结点的数据域 -> 将新结点的后继指针指向哨兵结点的后继结点 -> 将哨兵结点的后继结点的前驱指针指向新结点 -> 将新结点的前驱指针指向哨兵 -> 将哨兵结点的后继指针指向新节点。
/** * @brief 双向循环链表中，在哨兵结点之后插入即为头插法 * * @param Guard 哨兵结点 * @param data 数据 * * @return 状态码：0为成功 **/ int insertHead(DoubleLinkedList** Guard, DataType data) { DoubleLinkedNode *newNode;//声明新结点 int code = isInit(Guard); if (code) { return code; } newNode = (DoubleLinkedNode*)malloc(sizeof(DoubleLinkedNode));//为新节点申请内存 if (isNodeNull(newNode)) { return isNodeNull(newNode); } newNode->data = data;//存储数据至新结点的数据域 newNode->next = (*Guard)->next;//将新结点的后继指针指向哨兵结点的后继结点 (*Guard)->next->last = newNode;//将哨兵结点的后继结点的前驱指针指向新结点 newNode->last = (*Guard);//将新结点的前驱指针指向哨兵 (*Guard)->next = newNode;//将哨兵结点的后继指针指向新节点 return 0; }
4.双向循环链表插入之尾插法
双向循环链表中，在哨兵结点之前插入即为尾插法。主要步骤为：声明新结点并开辟内存 -> 存储数据至新结点的数据域 -> 将新节点前驱指针指向哨兵结点的前驱结点 -> 将哨兵结点的前驱结点的后继指针指向新节点 -> 将新节点的后继指针指向哨兵结点 -> 将哨兵结点的前驱指针指向新节点。
/** * @brief 双向循环链表中，在哨兵结点之前插入即为尾插法 * * @param Guard 哨兵结点 * @param data 数据 * * @return 状态码：0为成功 **/ int insertTail(DoubleLinkedList** Guard, DataType data) { DoubleLinkedNode *newNode;//声明新结点 int code = isInit(Guard); if (code) { return code; } newNode = (DoubleLinkedNode*)malloc(sizeof(DoubleLinkedNode));//为新节点申请内存 if (isNodeNull(newNode)) { return isNodeNull(newNode); } newNode->data = data;//存储数据至新结点的数据域 newNode->last = (*Guard)->last;//将新节点前驱指针指向哨兵结点的前驱结点 (*Guard)->last->next = newNode;//将哨兵结点的前驱结点的后继指针指向新节点 newNode->next = (*Guard);//将新节点的后继指针指向哨兵结点 (*Guard)->last = newNode;//将哨兵结点的前驱指针指向新节点 return 0; }
5.双向循环链表插入之选择插入
选择插入则为遍历链表直至插入位置的前一个结点。并修改前后指针的指向。
/** * @brief 链表选择插入 * * @param Guard 哨兵结点 * @param site 插入位置 * @param data 插入元素 * * @return 状态码：0为成功 **/ int insertSelect(DoubleLinkedList** Guard, int site, DataType data) { int code = check(Guard, site, 1); if (code) { return code; } int length = 0; DoubleLinkedNode* temp = (*Guard); DoubleLinkedNode* newNode = (DoubleLinkedNode*)malloc(sizeof(DoubleLinkedNode)); code = isNodeNull(newNode); if (code) { return code; } while (length < site) { if (length == (site - 1)) { newNode->data = data; newNode->next = temp->next; temp->next->last = newNode; newNode->last = temp; temp->next = newNode; } else { temp = temp->next; } length++; } return 0; }
6.双向循环链表之元素变更
元素变更也是通过遍历链表找到变更位置的结点，再修改数据域即可。
/** * @brief 变更指定位置的元素 * * @param Guard 哨兵结点 * @param site 变更位置 * @param data 变更元素 * * @return 状态码：0为成功 **/ int update(DoubleLinkedList** Guard, int site, DataType data) { int code = check(Guard, site, 1); if (code) { return code; } DoubleLinkedNode* temp = (*Guard); for (int i = 0; i < site; i++) { temp = temp->next; } temp->data = data; return 0; }
7.双向循环链表之结点删除
通过遍历链表直至删除位置的前一个结点，新建指针变量存储删除结点，修改指针指向后将该结点释放。
/** * @brief 删除指定位置的元素 * * @param Guard 哨兵结点 * @param site 删除位置 * * @return 状态码：0为成功 **/ int expurgate(DoubleLinkedList** Guard, int site) { int code = check(Guard, site, 1); if (code) { return code; } int length = 0; DoubleLinkedNode* temp = (*Guard); DoubleLinkedNode* target = (*Guard); while (length < site) { if (length == (site - 1)) { target = temp->next; temp->next = target->next; temp->next->last = temp; free(target); } length++; } return 0; }
8.双向循环链表之获取元素
遍历链表获取元素。
/** * @brief 获取指定结点的元素 * * @param Guard 哨兵结点 * @param site 操作位置 * * @return 数据元素 **/ DataType get(DoubleLinkedList** Guard, int site) { int code = check(Guard, site, 1); if (code) { return code; } DoubleLinkedNode* temp = (*Guard); for (int i = 0; i < site; i++) { temp = temp->next; } return temp->data; }
9.双向循环链表之元素查找
遍历链表进行判断并打印。
/** * @brief 元素查找 * * @param Guard 哨兵结点 * @param data 查找元素 * * @return 状态码：0为成功 **/ int find(DoubleLinkedList** Guard, DataType data) { if (getSize(Guard) == 0) { printf("ERROR[100004]：链表为空！\n\n"); return 100004; } int length = 0; int flag = 0; DoubleLinkedNode* temp = (*Guard)->next; while (length < getSize(Guard)) { if (temp->data == data) { printf("元素%d已找到,位置为%d\n\n", data, (length + 1)); flag = 1; } length++; } if (!flag) { printf("元素不存在！\n\n"); } return 0; }
10.双向循环链表之清空链表
遍历链表直至哨兵结点，同时挨个清空各节点。最后将哨兵结点的前驱后继指针再次指向自己。
/** * @brief 清空链表 * * @param Guard 哨兵元素 * * @return 状态码：0为成功 **/ int clear(DoubleLinkedList** Guard) { int code = isInit(Guard); if (code) { return code; } DoubleLinkedNode* target = (*Guard)->next; DoubleLinkedNode* temp = target->next; for (int i = 0; i < getSize(Guard); i++) { if (target != (*Guard)) { free(target); target = temp; temp = temp->next; } } (*Guard)->next = (*Guard)->last = *Guard; printf("链表已清空！\n\n"); return 0; }
10.双向循环链表之打印链表
遍历链表并打印各个元素。
/** * @brief 打印链表 * * @param Guard 哨兵结点 * * @return 状态码：0为成功 **/ int print(DoubleLinkedList** Guard) { int code = isInit(Guard); if (code) { return code; } int length = getSize(Guard); if (length == 0) { printf("ERROR[100004]：链表为空！\n\n"); return 100004; } DoubleLinkedNode* temp = (*Guard)->next; printf("链表为： "); for (int i = 0; i < length; i++) { printf("%d <=>", temp->data); temp = temp->next; } printf("\n\n"); return 0; }
四、完整Demo
Welcome.h（欢迎字符图案）:
char *welcome[] = { " \n", " 4&(\n", " ` ~&&\\yM#1\n", " ,_'Q!!NMW&\n", " WCb 7N@4D Q%,,\n", " PM'*MDk#M0p,\n", " ]@J0&e~~4r' ,+bQEQ\n", " F8I&#' _&B$$bW#&$\n", " &0A1 L#DE&E~!Q&Q,\n", " _=, ,#0RN1 _T@0$' ZN$Q. grNq5\n", " ^ 'd ,0K0pK^ g*Q0g' #Q4p&,/g9X*&#,_/ (q\n", " TA1 ,sDQWh4^ x&NM0` _ #FQ#K#fA# `*K#XWP~-\n", " ^&p,wNMM0qD: /HE#EN' ..#g)~ '@NG0Qx, `=X*\n", " ' '43$'hEk##m0D04f_g ~^ ~ `-00**0\n", " =0#ONq2W0BF^#, _ p,,\n", " ` ^''~ ~b'' **R3`\n", " ow,F +#F~'\n", " /-9! `\\ \n", " R\n" };
DoubleLinkedList.h（结构与函数声明）：
/** * DoubguardeguardinkedList.h 循环双向链表 **/ typedef int DataType; typedef struct node { DataType data;//数据域 struct node* last;//前驱指针 struct node* next;//后继指针 }DoubleLinkedNode, DoubleLinkedList; /** * 函数声明 **/ int init(DoubleLinkedList** Guard);//初始化链表 int isInit(DoubleLinkedList** Guard);//初始化判断 int getSize(DoubleLinkedList** Guard);//获取当前存储的数据长度 int insertHead(DoubleLinkedList** Guard, DataType data); //链表头插法，data为需要插入的数据 int insertTail(DoubleLinkedList** Guard, DataType data); //链表尾插法，data为需要插入的数据 int insertSelect(DoubleLinkedList** Guard, int site,DataType data); //链表选择插入，data为需要插入的数据 int isNodeNull(DoubleLinkedNode*);//节点内存申请判断 int update(DoubleLinkedList** Guard, int site, DataType data);//变更链表元素 int expurgate(DoubleLinkedList** Guard, int site);//移除site上的数据 int check(DoubleLinkedList** Guard, int site, int state);//操作位置合法性判断,state为1即为插入操作 DataType get(DoubleLinkedList** Guard, int site);//获取第site上的数据 int find(DoubleLinkedList** Guard, DataType data);//查找链表中是否存在该元素 int clear(DoubleLinkedList** Guard); //清空链表 int print(DoubleLinkedList** Guard);//打印链表
DoubleLinkedList.c（函数实现）：
#include <stdio.h> #include <stdlib.h> #include "DoubleLinkedList.h" /** * @brief 初始化 * * @param Guard 哨兵节点 * * @return 状态码：0为成功 **/ int init(DoubleLinkedList** Guard) { *Guard = (DoubleLinkedList*)malloc(sizeof(DoubleLinkedList)); int code = isInit(Guard); if (code) { return code; } (*Guard)->next = (*Guard)->last = *Guard;//循环链表初始化时，哨兵前驱后继指向自己 return 0; } /** * @brief 初始化判断 * * @param Guard Guard 哨兵结点 * * @return 状态码：0为成功 **/ int isInit(DoubleLinkedList** Guard) { if (*Guard == NULL) { printf("ERROR[100001]：申请内存错误，初始化失败！\n\n"); return 100001; } return 0; } /** * @brief 遍历并计算双向链表长度 * * @param Guard 哨兵结点 * * @return 链表长度 **/ int getSize(DoubleLinkedList** Guard) { int code = isInit(Guard); if (code) { return code; } int length = 0; DoubleLinkedNode* node = (*Guard)->next; while (node != (*Guard)) { //循环链表后继指针指向哨兵结点即为遍历结束 length++; node = node->next; } return length; } /** * @brief 双向循环链表中，在哨兵结点之后插入即为头插法 * * @param Guard 哨兵结点 * @param data 数据 * * @return 状态码：0为成功 **/ int insertHead(DoubleLinkedList** Guard, DataType data) { DoubleLinkedNode *newNode;//声明新结点 int code = isInit(Guard); if (code) { return code; } newNode = (DoubleLinkedNode*)malloc(sizeof(DoubleLinkedNode));//为新节点申请内存 if (isNodeNull(newNode)) { return isNodeNull(newNode); } newNode->data = data;//存储数据至新结点的数据域 newNode->next = (*Guard)->next;//将新结点的后继指针指向哨兵结点的后继结点 (*Guard)->next->last = newNode;//将哨兵结点的后继结点的前驱指针指向新结点 newNode->last = (*Guard);//将新结点的前驱指针指向哨兵 (*Guard)->next = newNode;//将哨兵结点的后继指针指向新节点 return 0; } /** * @brief 循环双向链表中，在哨兵结点之前插入即为尾插法 * * @param Guard 哨兵结点 * @param data 数据 * * @return 状态码：0为成功 **/ int insertTail(DoubleLinkedList** Guard, DataType data) { DoubleLinkedNode *newNode;//声明新结点 int code = isInit(Guard); if (code) { return code; } newNode = (DoubleLinkedNode*)malloc(sizeof(DoubleLinkedNode));//为新节点申请内存 if (isNodeNull(newNode)) { return isNodeNull(newNode); } newNode->data = data;//存储数据至新结点的数据域 newNode->last = (*Guard)->last;//将新节点前驱指针指向哨兵结点的前驱结点 (*Guard)->last->next = newNode;//将哨兵结点的前驱结点的后继指针指向新节点 newNode->next = (*Guard);//将新节点的后继指针指向哨兵结点 (*Guard)->last = newNode;//将哨兵结点的前驱指针指向新节点 return 0; } /** * @brief 链表选择插入 * * @param Guard 哨兵结点 * @param site 插入位置 * @param data 插入元素 * * @return 状态码：0为成功 **/ int insertSelect(DoubleLinkedList** Guard, int site, DataType data) { int code = check(Guard, site, 1); if (code) { return code; } int length = 0; DoubleLinkedNode* temp = (*Guard); DoubleLinkedNode* newNode = (DoubleLinkedNode*)malloc(sizeof(DoubleLinkedNode)); code = isNodeNull(newNode); if (code) { return code; } while (length < site) { if (length == (site - 1)) { newNode->data = data; newNode->next = temp->next; temp->next->last = newNode; newNode->last = temp; temp->next = newNode; } else { temp = temp->next; } length++; } return 0; } /** * @brief 变更指定位置的元素 * * @param Guard 哨兵结点 * @param site 变更位置 * @param data 变更元素 * * @return 状态码：0为成功 **/ int update(DoubleLinkedList** Guard, int site, DataType data) { int code = check(Guard, site, 1); if (code) { return code; } DoubleLinkedNode* temp = (*Guard); for (int i = 0; i < site; i++) { temp = temp->next; } temp->data = data; return 0; } /** * @brief 结点内存申请判断 * * * @return 状态码：0为成功 **/ int isNodeNull(DoubleLinkedNode* node) { if (node == NULL) { printf("ERROR[100002]：申请内存错误，结点创建失败！\n\n"); return 100002; } return 0; } /** * @brief 删除指定位置的元素 * * @param Guard 哨兵结点 * @param site 删除位置 * * @return 状态码：0为成功 **/ int expurgate(DoubleLinkedList** Guard, int site) { int code = check(Guard, site, 1); if (code) { return code; } int length = 0; DoubleLinkedNode* temp = (*Guard); DoubleLinkedNode* target = (*Guard); while (length < site) { if (length == (site - 1)) { target = temp->next; temp->next = target->next; temp->next->last = temp; free(target); } length++; } return 0; } /** * @brief 操作位置合法性判断 * * @param Guard 哨兵结点 * @param site 操作位置 * @param state 操作状态，1为插入操作，0为更新 || 删除 || 获取 * * @return 状态码：0为成功 **/ int check(DoubleLinkedList** Guard, int site, int state) { int code = isInit(Guard); if (code) { return code; } int limit; if (state == 1) { limit = (getSize(Guard) + 1); } else { limit = getSize(Guard); } if (site > limit || site < 1) { printf("ERROR[100003]：操作位置不合法！\n\n"); return 100003; } return 0; } /** * @brief 获取指定结点的元素 * * @param Guard 哨兵结点 * @param site 操作位置 * * @return 数据元素 **/ DataType get(DoubleLinkedList** Guard, int site) { int code = check(Guard, site, 1); if (code) { return code; } DoubleLinkedNode* temp = (*Guard); for (int i = 0; i < site; i++) { temp = temp->next; } return temp->data; } /** * @brief 元素查找 * * @param Guard 哨兵结点 * @param data 查找元素 * * @return 状态码：0为成功 **/ int find(DoubleLinkedList** Guard, DataType data) { if (getSize(Guard) == 0) { printf("ERROR[100004]：链表为空！\n\n"); return 100004; } int length = 0; int flag = 0; DoubleLinkedNode* temp = (*Guard)->next; while (length < getSize(Guard)) { if (temp->data == data) { printf("元素%d已找到,位置为%d\n\n", data, (length + 1)); flag = 1; } length++; } if (!flag) { printf("元素不存在！\n\n"); } return 0; } /** * @brief 清空链表 * * @param Guard 哨兵元素 * * @return 状态码：0为成功 **/ int clear(DoubleLinkedList** Guard) { int code = isInit(Guard); if (code) { return code; } DoubleLinkedNode* target = (*Guard)->next; DoubleLinkedNode* temp = target->next; for (int i = 0; i < getSize(Guard); i++) { if (target != (*Guard)) { free(target); target = temp; temp = temp->next; } } (*Guard)->next = (*Guard)->last = *Guard; printf("链表已清空！\n\n"); return 0; } /** * @brief 打印链表 * * @param Guard 哨兵结点 * * @return 状态码：0为成功 **/ int print(DoubleLinkedList** Guard) { int code = isInit(Guard); if (code) { return code; } int length = getSize(Guard); if (length == 0) { printf("ERROR[100004]：链表为空！\n\n"); return 100004; } DoubleLinkedNode* temp = (*Guard)->next; printf("链表为： "); for (int i = 0; i < length; i++) { printf("%d <=>", temp->data); temp = temp->next; } printf("\n\n"); return 0; }
Main.c（主函数）：
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "welcome.h" #include "DoubleLinkedList.h" /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int main(int argc, char *argv[]) { for (int i = 0; i < 19; i++) { printf("%s", welcome[i]); for (int j = 0; j <= 100000000; j++) { for (int m; m <= 100000000; m++) { ; } } } int operate; int site; DataType data; DoubleLinkedList* Guard; printf("\n\n本应用程序为数据结构-链表演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n"); do { printf("<----------------------------------------------------链表演示程序--------------------------------------------------->\n"); printf("0. 退出程序\n"); printf("1. 初始化链表\n"); printf("2. 打印链表\n"); printf("3. 选择插入\n"); printf("4. 删除元素\n"); printf("5. 查找元素\n"); printf("6. 变更元素\n"); printf("7. 获取元素\n"); printf("8. 头插法\n"); printf("9. 尾插法\n"); printf("10. 链表长度查询\n"); printf("11. 清空链表\n"); printf("12. 帮助\n"); printf("请输入操作选项(0~11,0为退出)："); scanf("%d", &operate); switch (operate) { case 1: if (!init(&Guard)) { printf("初始化完成\n\n"); } break; case 2: print(&Guard); break; case 3: printf("请输入插入位置与插入数据（以逗号间隔）："); scanf("%d,%d", &site, &data); insertSelect(&Guard, site, data); break; case 4: printf("请输入删除位置："); scanf("%d", &site); expurgate(&Guard, site); break; case 5: printf("请输入查找元素："); scanf("%d", &data); find(&Guard, data); break; case 6: printf("请输入更新位置与更新元素（以逗号间隔）："); scanf("%d,%d", &site, &data); update(&Guard, site, data); break; case 7: printf("请输入需要获取的位置："); scanf("%d", &site); printf("该位置元素为%d\n", get(&Guard, site)); break; case 8: printf("请输入插入数据："); scanf("%d", &data); insertHead(&Guard, data); break; case 9: printf("请输入插入数据："); scanf("%d", &data); insertTail(&Guard, data); break; case 10: printf("链表的长度为：%d\n", getSize(&Guard)); break; case 11: clear(&Guard); break; case 12: printf("本应用程序为数据结构-链表演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n"); break; case 0: return 0; break; } } while (operate != 0); return 0; }
五、运行截图
图3 程序运行截图
六、小结
- 双向循环链表的任意元素都有一个前驱和一个后继，所有数据元素在关系上构成逻辑上的环。双向循环链表是一种特殊的链表，尾结点的后继指针指向哨兵结点的地址，哨兵结点的前驱指针又指向尾结点。
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
- 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后或向后顺序扫描其余结点，双向的遍历方式相较于单链表与顺序表更为灵活。
写给自己的闲篇：本周好像更忙了，再坚持一下把手里的活干完，回归到自律的生活。加油~
七、参考文献
王海艳等.《数据结构（C语言）》第二版[M].北京:人民邮电出版社,2020:10~14.