跳到主要内容数据结构初阶：详解线性表之双链表 | 极客日志C算法
数据结构初阶：详解线性表之双链表
综述由AI生成双向带头结点循环链表是线性表的常见实现方式之一。其概念、节点结构定义及基本操作实现。内容包括初始化、长度计算、头尾插、指定位置插入删除、查找修改及销毁操作。通过 C 语言代码示例展示了指针连接逻辑与内存管理细节，重点解决了双向链表指针维护的复杂性，适用于 C 语言数据结构学习。
星云25 浏览 数据结构初阶：详解线性表之双链表
1、双链表的概念
双链表由两个指针组成，一个指向下一个节点，一个指向前一个节点。结构上与单链表相似，包含数据域和指针域。
因为是双向带头结点循环链表，整个链表结构如下所示（头结点作为哨兵位）：
2、双链表的基本实现
2.1、双向链表节点的创建
与单链表类似，先申请内存空间并初始化元素。由于有两个指针，初始化时需注意指向关系。
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;
}
2.2、双向链表的初始化
采用带头节点的双向链表，只需对哨兵位进行初始化。
DListNode* Init_DListNode() {
DListNode* phead = Buy_Node(-1);
if (phead == NULL) {
printf("头节点创建失败...\n");
return NULL;
}
return phead;
}
2.3、双向链表长度的计算
遍历一遍链表并用计数器统计，注意从正式节点开始，不包含哨兵位。
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;
}
2.4、双向链表的插入操作
2.4.1、头部插入
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;
}
2.4.2、尾部插入
在最后一个节点与头结点之间插入。利用哨兵位的 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;
}
2.4.3、查找 pos 位置的元素
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;
}
2.4.4、pos 位置插入
2.4.4.1、pos 位置之前插入
若 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;
}
2.4.4.2、pos 位置之后插入
若 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;
}
2.5、双向链表的删除操作
2.5.1、头部删除
删除第一个正式节点，让哨兵位与第二个正式节点相连。
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;
}
2.5.2、尾部删除
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;
}
2.5.3、pos 位置删除
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;
}
2.6、双向链表的元素查找
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");
}
2.7、双向链表的修改
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;
}
2.8、双向链表的打印
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;
}
}
2.9、双向链表的销毁
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;
}
3、代码总和
#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;
}
以上就是我对双向链表所有内容的分享了，感谢阅读。如有描述不当之处，恳请指正。
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
