双向带头结点循环链表是线性表的常见实现方式之一。本文详细介绍了其概念、节点结构定义及基本操作实现。内容包括初始化、长度计算、头尾插、指定位置插入删除、查找修改及销毁操作。通过 C 语言代码示例展示了指针连接逻辑与内存管理细节，重点解决了双向链表指针维护的复杂性，适用于 C 语言数据结构学习。
双链表由两个指针组成，一个指向下一个节点，一个指向前一个节点。结构上与单链表相似，包含数据域和指针域。
因为是双向带头结点循环链表，整个链表结构如下所示（头结点作为哨兵位）：
与单链表类似，先申请内存空间并初始化元素。由于有两个指针，初始化时需注意指向关系。
DListNode* Buy_Node(Elemtype data) {
DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));
if (newNode == NULL) {
printf("新节点创建失败...\n");
return NULL;
}
newNode->next = newNode;
newNode->data = data;
newNode->front = newNode;
return newNode;
}
采用带头节点的双向链表，只需对哨兵位进行初始化。
DListNode* Init_DListNode() {
DListNode* phead = Buy_Node(-1);
if (phead == NULL) {
printf("头节点创建失败...\n");
return NULL;
}
return phead;
}
遍历一遍链表并用计数器统计，注意从正式节点开始，不包含哨兵位。
int Get_DListlength(DListNode* phead) {
DListNode* pcur = phead;
int count = 0;
if (pcur->next == phead) {
return 0;
}
while (pcur->next != phead) {
pcur = pcur->next;
count++;
}
return count;
}
将新节点插入到哨兵位与第一个正式节点之间。
void Push_Front(DListNode* phead, Elemtype data) {
assert(phead);
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) {
printf("新的头插节点创建失败...\n");
return;
}
// 连接新节点指针
newNode->next = phead->next;
newNode->front = phead;
// 断开旧节点连接并重新连接
phead->next->front = newNode;
phead->next = newNode;
}
在最后一个节点与头结点之间插入。利用哨兵位的 front 指针直接找到尾结点。
void Push_Back(DListNode* phead, Elemtype data) {
assert(phead);
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) {
printf("尾插节点创建失败...\n");
return;
}
DListNode* ptail = phead->front;
// 连接新节点指针
newNode->front = ptail;
newNode->next = phead;
// 更新旧节点指针
ptail->next = newNode;
phead->front = newNode;
}
辅助函数，用于定位指定位置节点。
DListNode* Search_elem_for_pos(DListNode* phead, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return NULL;
}
DListNode* pcur = phead->next;
for (int i = 1; i < pos; i++) {
if (pcur->next == phead) {
printf("pos 位置没有元素...\n");
return NULL;
}
pcur = pcur->next;
}
return pcur;
}
若 pos 为 1，等同于头插；否则在目标节点前插入。
void Push_pos_Front(DListNode* phead, Elemtype data, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
if (pos == 1) {
Push_Front(phead, data);
return;
}
DListNode* ppos = Search_elem_for_pos(phead, pos);
if (ppos == NULL) {
return;
}
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) return;
newNode->next = ppos;
newNode->front = ppos->front;
ppos->front->next = newNode;
ppos->front = newNode;
}
若 pos 为 1，等同于尾插；否则在目标节点后插入。
void Push_pos_Back(DListNode* phead, Elemtype data, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
if (pos == 1) {
Push_Back(phead, data);
return;
}
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) {
return;
}
DListNode* ppos = Search_elem_for_pos(phead, pos);
if (ppos == NULL) {
return;
}
newNode->next = ppos->next;
newNode->front = ppos;
ppos->next->front = newNode;
ppos->next = newNode;
}
删除第一个正式节点，让哨兵位与第二个正式节点相连。
void Pop_Front(DListNode* phead) {
assert(phead);
int len = Get_DListlength(phead);
if (len == 0) {
printf("链表为空，无法删除...\n");
return;
}
DListNode* delet = phead->next;
phead->next = phead->next->next;
phead->next->next->front = phead;
free(delet);
delet = NULL;
}
处理被删除节点与不删除节点之间的关系。
void Pop_Back(DListNode* phead) {
assert(phead);
int len = Get_DListlength(phead);
if (len == 0) {
printf("链表为空，无法删除...\n");
return;
}
DListNode* delet = phead->front;
delet->front->next = phead;
phead->front = delet->front;
free(delet);
delet = NULL;
}
直接删除指定位置节点。
void Pop_Pos(DListNode* phead, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
if (pos == 1) {
Pop_Front(phead);
return;
}
if (pos == len) {
Pop_Back(phead);
return;
}
DListNode* delet = Search_elem_for_pos(phead, pos);
if (delet == NULL) {
return;
}
delet->front->next = delet->next;
delet->next->front = delet->front;
free(delet);
delet = NULL;
}
遍历链表查找是否存在指定数据。
void Search_elem(DListNode* phead, Elemtype data) {
assert(phead);
int len = Get_DListlength(phead);
if (len == 0) {
printf("当前链表为空，没有元素可以查找...\n");
return;
}
DListNode* pcur = phead->next;
while (pcur != phead) {
if (pcur->data == data) {
printf("找到了!!!\n");
return;
}
pcur = pcur->next;
}
printf("找不到...\n");
}
修改指定位置元素的值。
void Change_elem(DListNode* phead, Elemtype data, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
DListNode* ppos = Search_elem_for_pos(phead, pos);
if (ppos == NULL) {
printf("想要修改的元素不存在\n");
return;
}
ppos->data = data;
}
遍历打印所有节点数据。
void my_printf(DListNode* phead) {
DListNode* pcur = phead->next;
if (pcur == phead) {
printf("当前链表内容为空...\n");
return;
}
while (pcur != phead) {
printf("%d ", pcur->data);
pcur = pcur->next;
}
}
遍历逐个释放节点内存。
void Destory_list(DListNode* phead) {
DListNode* pcur = phead->next;
while (pcur != phead) {
DListNode* delet = pcur;
pcur = pcur->next;
free(delet);
delet = NULL;
}
free(phead);
phead = NULL;
}
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<assert.h>
typedef int Elemtype;
typedef struct DListNode {
Elemtype data;
struct DListNode* front;
struct DListNode* next;
}DListNode;
// 函数声明
DListNode* Init_DListNode();
int Get_DListlength(DListNode* phead);
void Push_Front(DListNode* phead, Elemtype data);
void Push_Back(DListNode* phead, Elemtype data);
void Push_pos_Front(DListNode* phead, Elemtype data, int pos);
void Push_pos_Back(DListNode* phead, Elemtype data, int pos);
void Pop_Front(DListNode* phead);
void Pop_Back(DListNode* phead);
void Pop_Pos(DListNode* phead, int pos);
DListNode* Search_elem_for_pos(DListNode* phead, int pos);
void Search_elem(DListNode* phead, Elemtype data);
void Change_elem(DListNode* phead, Elemtype data, int pos);
void my_printf(DListNode* phead);
void Destory_list(DListNode* phead);
// 实现部分
int Get_DListlength(DListNode* phead) {
DListNode* pcur = phead;
int count = 0;
if (pcur->next == phead) {
return 0;
}
while (pcur->next != phead) {
pcur = pcur->next;
count++;
}
return count;
}
DListNode* Buy_Node(Elemtype data) {
DListNode* newNode = (DListNode*)malloc(sizeof(DListNode));
if (newNode == NULL) {
printf("新节点创建失败...\n");
return NULL;
}
newNode->next = newNode;
newNode->data = data;
newNode->front = newNode;
return newNode;
}
DListNode* Init_DListNode() {
DListNode* phead = Buy_Node(-1);
if (phead == NULL) {
printf("头节点创建失败...\n");
return NULL;
}
return phead;
}
void Push_Front(DListNode* phead, Elemtype data) {
assert(phead);
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) {
printf("新的头插节点创建失败...\n");
return;
}
newNode->next = phead->next;
newNode->front = phead;
phead->next->front = newNode;
phead->next = newNode;
}
void Push_Back(DListNode* phead, Elemtype data) {
assert(phead);
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) {
printf("尾插节点创建失败...\n");
return;
}
DListNode* ptail = phead->front;
newNode->front = ptail;
newNode->next = phead;
ptail->next = newNode;
phead->front = newNode;
}
DListNode* Search_elem_for_pos(DListNode* phead, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return NULL;
}
DListNode* pcur = phead->next;
for (int i = 1; i < pos; i++) {
if (pcur->next == phead) {
printf("pos 位置没有元素...\n");
return NULL;
}
pcur = pcur->next;
}
return pcur;
}
void Push_pos_Front(DListNode* phead, Elemtype data, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
if (pos == 1) {
Push_Front(phead, data);
return;
}
DListNode* ppos = Search_elem_for_pos(phead, pos);
if (ppos == NULL) {
return;
}
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) return;
newNode->next = ppos;
newNode->front = ppos->front;
ppos->front->next = newNode;
ppos->front = newNode;
}
void Push_pos_Back(DListNode* phead, Elemtype data, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
if (pos == 1) {
Push_Back(phead, data);
return;
}
DListNode* newNode = Buy_Node(data);
if (newNode == NULL) {
return;
}
DListNode* ppos = Search_elem_for_pos(phead, pos);
if (ppos == NULL) {
return;
}
newNode->next = ppos->next;
newNode->front = ppos;
ppos->next->front = newNode;
ppos->next = newNode;
}
void Pop_Front(DListNode* phead) {
assert(phead);
int len = Get_DListlength(phead);
if (len == 0) {
printf("链表为空，无法删除...\n");
return;
}
DListNode* delet = phead->next;
phead->next = phead->next->next;
phead->next->next->front = phead;
free(delet);
delet = NULL;
}
void Pop_Back(DListNode* phead) {
assert(phead);
int len = Get_DListlength(phead);
if (len == 0) {
printf("链表为空，无法删除...\n");
return;
}
DListNode* delet = phead->front;
delet->front->next = phead;
phead->front = delet->front;
free(delet);
delet = NULL;
}
void Pop_Pos(DListNode* phead, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
if (pos == 1) {
Pop_Front(phead);
return;
}
if (pos == len) {
Pop_Back(phead);
return;
}
DListNode* delet = Search_elem_for_pos(phead, pos);
if (delet == NULL) {
return;
}
delet->front->next = delet->next;
delet->next->front = delet->front;
free(delet);
delet = NULL;
}
void Change_elem(DListNode* phead, Elemtype data, int pos) {
assert(phead);
int len = Get_DListlength(phead);
if (pos < 1 || pos > len) {
printf("pos 值不合法...\n");
return;
}
DListNode* ppos = Search_elem_for_pos(phead, pos);
if (ppos == NULL) {
printf("想要修改的元素不存在\n");
return;
}
ppos->data = data;
}
void Search_elem(DListNode* phead, Elemtype data) {
assert(phead);
int len = Get_DListlength(phead);
if (len == 0) {
printf("当前链表为空，没有元素可以查找...\n");
return;
}
DListNode* pcur = phead->next;
while (pcur != phead) {
if (pcur->data == data) {
printf("找到了!!!\n");
return;
}
pcur = pcur->next;
}
printf("找不到...\n");
}
void my_printf(DListNode* phead) {
DListNode* pcur = phead->next;
if (pcur == phead) {
printf("当前链表内容为空...\n");
return;
}
while (pcur != phead) {
printf("%d ", pcur->data);
pcur = pcur->next;
}
}
void Destory_list(DListNode* phead) {
DListNode* pcur = phead->next;
while (pcur != phead) {
DListNode* delet = pcur;
pcur = pcur->next;
free(delet);
delet = NULL;
}
free(phead);
phead = NULL;
}
int main() {
DListNode* phead = Init_DListNode();
int choose = 0;
do {
system("cls");
printf("================================================================\n");
printf(" ***带头节点双向循环链表*** \n");
printf("插入:\n");
printf("1.头插 2.尾插 3.Pos 位置之前插入 4.pos 位置之后插入\n");
printf("删除:\n");
printf("5.头删 6.尾删 7.pos 位置删除\n");
printf("其他:\n");
printf("8.查找 9.修改\n");
printf("================================================================\n");
printf("\n");
printf("当前的链表为:\n");
my_printf(phead);
printf("\n");
printf("请输入你的选择 (按 -1 结束程序):\n");
scanf("%d", &choose);
switch (choose) {
case 1: {
printf("请输入你想输入元素的个数:\n");
int num = 0;
Elemtype data = 0;
scanf("%d", &num);
printf("请输入你想输入的元素：\n");
for (int i = 0; i < num; i++) {
scanf("%d", &data);
Push_Front(phead, data);
}
Sleep(1000);
printf("插入成功！！！\n");
Sleep(2000);
break;
}
case 2: {
printf("请输入你想输入元素的个数:\n");
int num = 0;
Elemtype data = 0;
scanf("%d", &num);
printf("请输入你想输入的元素：\n");
for (int i = 0; i < num; i++) {
scanf("%d", &data);
Push_Back(phead, data);
}
Sleep(1000);
printf("插入成功！！！\n");
Sleep(2000);
break;
}
case 3: {
printf("请输入 pos:\n");
int pos = 0;
scanf("%d", &pos);
Elemtype data = 0;
printf("请输入你想输入的元素：\n");
scanf("%d", &data);
Push_pos_Front(phead, data, pos);
Sleep(1000);
printf("插入成功！！！\n");
Sleep(2000);
break;
}
case 4: {
printf("请输入 pos:\n");
int pos = 0;
scanf("%d", &pos);
Elemtype data = 0;
printf("请输入你想输入的元素：\n");
scanf("%d", &data);
Push_pos_Back(phead, data, pos);
Sleep(1000);
printf("插入成功！！！\n");
Sleep(2000);
break;
}
case 5: {
Pop_Front(phead);
printf("删除成功！\n");
Sleep(2000);
break;
}
case 6: {
Pop_Back(phead);
printf("删除成功！\n");
Sleep(2000);
break;
}
case 7: {
printf("请输入你想删除的位置：\n");
int pos = 0;
scanf("%d", &pos);
Pop_Pos(phead, pos);
printf("删除成功！\n");
Sleep(2000);
break;
}
case 8: {
printf("请输入你想查找的元素：\n");
Elemtype data = 0;
scanf("%d", &data);
Search_elem(phead, data);
Sleep(2000);
break;
}
case 9: {
printf("请输入你向修改之后的元素：\n");
Elemtype data = 0;
scanf("%d", &data);
printf("请输入你想修改的位置：\n");
int pos = 0;
scanf("%d", &pos);
Change_elem(phead, data, pos);
printf("修改成功!\n");
Sleep(2000);
break;
}
case -1: {
printf("正在退出程序...\n");
Sleep(2000);
printf("退出成功!!!\n");
Sleep(2000);
break;
}
}
} while (choose != -1);
Destory_list(phead);
return 0;
}
以上就是我对双向链表所有内容的分享了，感谢阅读。如有描述不当之处，恳请指正。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online