· 链表最终章双向链表及其应用

链表最终章双向链表及其应用

1245 字
6 分钟
链表最终章双向链表及其应用
StarryLin/Geek · 摘要

本文讲解带头节点的双向循环链表，用静态函数封装插入与删除，并实现初始化、头尾插、查找删除、展示和销毁，说明双向结构虽增加代码复杂度但操作更便捷。
2026-06-21
数据结构
数据结构

———————————本文旨在交流探讨计算机知识，欢迎交流指正———————————— 上一章，我们介绍了链表的循环扩展，但是，单向链表毕竟是单向查询的，就算是经过循环来查找，终究是效率偏低，下面，我们来介绍一种工程项目中运用更加广泛的一种链表结构：双向链表——： 根据此结构，我们可以发现，虽然代码复杂度增加了，但是由于此结构是双向的，操作更加便捷，下面，我将演示各模块内容： 首先，是结构的构建：

typedef int Element;
typedef struct _node {
Element val;
struct _node *next;
struct _node *prev;
} DNode, DList;


/* 使用一个带头节点的双向循环链表，头节点让用户来管理，提供初始化接口 */
void initDList(DList *header);
void releaseDList(DList *header);


// 实现头插、尾插
void insertDListHeader(DList *header, Element val);
void insertDListRear(DList *header, Element val);
// 显示链表
void showDList(const DList *header);
// 删除一个元素
void delDList(DList *header, Element e);

注：此为.h头文件里的内容，若先用头文件封装再放在.c文件里面使用，最后在main.c文件里面测试，很好的保证了产品内容的安全性与代码便捷性。 1、这一次，为了让代码更加简洁规范，我们使用static的模式构建加入和删除两大基本模块：

//next是已知的待插入位置节点的下一个节点；
//prev是已知的待插入节点的上一个节点（前置节点）；


//插入
static void addDNode(DNode *new_node, DNode *prev, DNode *next) {
next->prev = new_node;//待插入节点下一个节点的上一个节点是新节点；
new_node->next = next;//新节点的下一个是上一个节点；
new_node->prev = prev;新节点上一个是前置节点
prev->next = new_node;前置节点下一个是新节点
}


//删除
static void delDNode(DNode *prev, DNode *next) {
next->prev = prev;//某节点下一个节点的前一个是某节点上一个节点；
prev->next = next;//某节点上一个节点的下一个是某节点下一个节点；
}

2、然后，我们再在此基础上完成增删改查的基本操作：

1、初始化：

void initDList(DList* header) {
 header->val = 0;//初始化头结点的数值域为0
 header->next = header->prev = header;//头结点的前置节点和后置节点都初始化指向头结点
}

2、增添操作：

void insertDListHeader(DList* header, Element val) {
 DNode *new_node = malloc(sizeof(DNode));//malloc申请空间建立一个新节点
 new_node->val = val;//新节点赋值；
 addDNode(new_node, header, header->next);//函数操作
 ++header->val;
}
//头插法;
void insertDListRear(DList* header, Element val) {
 DNode *new_node = malloc(sizeof(DNode));
 new_node->val = val;
 addDNode(new_node, header->prev, header);
 ++header->val;
}
//尾插法；

3、删除操作

void delDList(DList* header, Element e) {
 // 1. 找到这个元素，就可以删除，不需要再找到前置节点
 DNode *pos = header->next;
 while (pos != header && pos->val != e) {
 pos = pos->next;
 }
 // 2. 找到没有？
 if (pos != header) { // 找到
 delDNode(pos->prev, pos->next);
 pos->next = pos->prev = NULL;
 free(pos);
 --header->val;
 } else {
 printf("Not find %d element!\n", e);
 }

4、展示函数（若对工程有疑问和对const有疑问可以看本专栏的第一篇内容）

void showDList(const DList* header) {
 DNode *pos = header->next;
 printf("show: ");
 while (pos != header) {
 printf("\t%d", pos->val);
 pos = pos->next;
 }
 printf("\n");
}
//简单的循环打印，不过多赘述；

5、最后，是销毁链表的函数：

void releaseDList(DList* header) {
 DNode *pos = header->next;
 DNode *tmp = NULL;
 while (pos != header) {
 tmp = pos;
 delDNode(pos->prev, pos->next);
 pos = pos->next;
 free(tmp);
 --header->val;
 }
}
//逐个销毁

最后附上各文件代码： 1、doubleList.h:

#ifndef DOUBLE_LIST_H
#define DOUBLE_LIST_H


typedef int Element;
typedef struct _node {
Element val;
struct _node *next;
struct _node *prev;
} DNode, DList;


/* 使用一个带头节点的双向循环链表，头节点让用户来管理，提供初始化接口 */
void initDList(DList *header);
void releaseDList(DList *header);


// 实现头插、尾插
void insertDListHeader(DList *header, Element val);
void insertDListRear(DList *header, Element val);
// 显示链表
void showDList(const DList *header);
// 删除一个元素
void delDList(DList *header, Element e);


#endif //DOUBLE_LIST_H

2、doubleList.c

#include "doubleList.h"//doubleList.h文件封装的函数名
#include
#include


static void addDNode(DNode *new_node, DNode *prev, DNode *next) {
next->prev = new_node;
new_node->next = next;
new_node->prev = prev;
prev->next = new_node;
}


static void delDNode(DNode *prev, DNode *next) {
next->prev = prev;
prev->next = next;
}


void initDList(DList* header) {
header->val = 0;
header->next = header->prev = header;
}


void releaseDList(DList* header) {
DNode *pos = header->next;
DNode *tmp = NULL;
while (pos != header) {
tmp = pos;
delDNode(pos->prev, pos->next);
pos = pos->next;
free(tmp);
--header->val;
}
}


void insertDListHeader(DList* header, Element val) {
DNode *new_node = malloc(sizeof(DNode));
new_node->val = val;
addDNode(new_node, header, header->next);
++header->val;
}


void insertDListRear(DList* header, Element val) {
DNode *new_node = malloc(sizeof(DNode));
new_node->val = val;
addDNode(new_node, header->prev, header);
++header->val;
}


void showDList(const DList* header) {
DNode *pos = header->next;
printf("show: ");
while (pos != header) {
printf("\t%d", pos->val);
pos = pos->next;
}
printf("\n");
}


void delDList(DList* header, Element e) {
// 1. 找到这个元素，就可以删除，不需要再找到前置节点
DNode *pos = header->next;
while (pos != header && pos->val != e) {
pos = pos->next;
}
// 2. 找到没有？
if (pos != header) { // 找到
delDNode(pos->prev, pos->next);
pos->next = pos->prev = NULL;
free(pos);
--header->val;
} else {
printf("Not find %d element!\n", e);
}
}

3、main.c

#include
#include "doubleList.h"


DList stu_table;


int main() {
initDList(&stu_table);


for (int i = 0; i < 5; ++i) {
// insertDListHeader(&stu_table, i + 100);
insertDListRear(&stu_table, i + 100);
}
insertDListHeader(&stu_table, 60);
insertDListHeader(&stu_table, 80);
showDList(&stu_table);
printf("====================\n");
delDList(&stu_table, 102);
showDList(&stu_table);
releaseDList(&stu_table);
printf("num: %d\n", stu_table.val);
showDList(&stu_table);
return 0;
}

————————————希望能对你有所帮助！！！————————————————

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

链表最终章双向链表及其应用
https://mjzy.tech/posts/knowledge/链表最终章双向链表及其应用/
作者
JIA
发布于
2026-06-21
许可协议
CC BY-NC-SA 4.0
计算机组成原理绪论
链表的实现与介绍
相关文章 智能推荐
1
拓展单向循环链表
数据结构 本文讲解单向循环链表的C语言实现，先分析带头结点与尾指针的结构设计，再给出初始化、头插、尾插、删除、遍历和销毁函数。边界是仅讨论实现思路，未展开约瑟夫环测试。
2
链表的实现与介绍
数据结构 本文介绍链表的结构与C语言实现，针对顺序表内存碎片问题引出链式存储。讲解节点数据域与地址域，给出初始化、按位插入、按值删除及遍历等函数代码。讨论限于无操作系统内存分配场景。
3
附录对于头结点单向链表的优化方法
数据结构 本文介绍无头结点单向链表的优化：用栈上dummy节点临时充当头结点，遍历或增删结束后还原header指针，使结构统一，并给出初始化、插入、删除及销毁实现。
4
顺序表的实现与介绍及部分工程思想的思考
数据结构 本文介绍堆空间动态顺序表的实现，含表头data、pos、capacity，用malloc和free管理，扩容两倍并搬移数据，讨论插入删除的搬移逻辑与防泄露的工程思想，并以测试验证。
5
数据结构之树及树的存储
数据结构 本文介绍树的基本概念与存储表示法：双亲表示法找父节点快、找孩子需遍历；孩子表示法相反；孩子兄弟表示法用二叉链表存左孩子右兄弟，便于查孩子和兄弟。
随机文章 随机推荐

评论区

分享你的想法，与大家交流讨论

正在加载 GitHub 评论…

Tips · 随手记
自动保存到此浏览器0
仅自己可见 · 每篇文章单独保存
© 2026 JIA. All Rights Reserved. / RSS / Sitemap
Built with Astro · Dusty Notes

文章目录