双向循环链表超详细讲解 | 带头节点&带头指针+完整可运行c语言代码

文章目录

• 双向循环链表
• • 1.带头节点的双向循环链表
  • • 前置知识
    • • ==1.插入相关==
      • ==2.删除相关==
    • 头文件部分
    • 实现
    • • 1.初始化表头
      • 2.释放数据域 头置空
      • 3.头插
      • 4.尾插
      • 5.显示链表
      • 6.删除一个元素
      • 测试案例
      • main函数
      • 输出结果
  • 2.带头指针的双向循环链表

双向循环链表

1.带头节点的双向循环链表

前置知识

所谓双向循环链表就是每个节点包含 前驱指针 prev + 后继指针 next , 尾节点的 next 指向头节点，头节点的 prev 指向尾节点，首尾互相绑定，形成环形闭环

​ 先展示下链表的样子

1.插入相关

​ 双向链表的插入有很多种写法 我展示我的写法 ——> 逆时针更新

next->prev = new_node
new_node->next = next;
new_node->prev = prev;
prev->next = new_node;

​

​

​ 其实我们可以把上面的插入代码封装成一个 接口 这样不论是头插还是尾插都可以直接调用

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;
}
//如果是头插的话 DNode *prev = header; DNode *next = header.next;
//如果是尾插的话 DNode *prev = header->prev; DNode *next = header;

//关于 指定位置插入的话 在单链表那里讲过 想实现的话具体可以自己去看下单链表那一节
//单向循环链表那里的指定位置插入也是 (上一节我竟然忘记写了😥😥)

2.删除相关

​ 这个其实就很简单了 直接上代码上图

next->prev=prev;
prev->next=next;
free(p);

​ 我们也把这个封装成接口吧

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

​ 小思考

其实最后我们可以思考下 这里的删除和单链表中的删除有哪些不同
单链表: 先找到前置节点… …
双向链表: 站到自己删自己

头文件部分

typedef int Element;

typedef struct _node {
Element val; //这个val在表头中是表节点数量 在节点中是数据域
struct _node *next;
struct _node *prev;
} DNode, DList; //节点和表头

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

//2.释放数据域 头置空
void releaseDList(DList *header);

//3.头插
void insertDListHeader(DList *header, Element val);

//4.尾插
void insertDListRear(DList *header, Element val);

//5.显示链表
void showDList(const DList *header);

//6.删除一个元素
void delDList(DList *header, Element e);

实现

1.初始化表头

void initDList(DList* header)
{
header->val = 0; //表中没节点
header->next = header->prev = header; //首尾相连
}

2.释放数据域 头置空

void releaseDList(DList* header)
{
//从第一个节点开始 一个个的删除
DNode *pos = header->next; //第一个节点
// tmp临时保存待释放节点，防止断链
DNode *tmp = NULL;

while (pos != header)
{
//因为要不断向后遍历至下一个节点 所以我们得备份一下pos (备份当前待删除节点地址)
//如果我们不备份的话 直接释放pos 那还怎么向后遍历呢??
tmp = pos;

//调用删除接口
delDNode(pos->prev, pos->next);

//遍历至下一个节点
pos = pos->next;
//释放该节点内存
free(tmp);

//减少表中的节点数量
—header->val;
}

printf("list num: %d", header->val);
//头置空
header->next = header->prev = NULL;
}

3.头插

//插入接口
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;
}

void insertDListHeader(DList* header, Element val)
{
//创建新节点
DNode *new_node = malloc(sizeof(DNode));

new_node->val = val;

//调用插入接口
addDNode(new_node, header, header->next);

//增加表中的节点数量
++header->val;
}

4.尾插

void insertDListRear(DList* header, Element val)
{
//创建新节点
DNode *new_node = malloc(sizeof(DNode));

new_node->val = val;

//调用插入接口
addDNode(new_node, header->prev, header);

//增加表中的节点数量
++header->val;
}

5.显示链表

void showDList(const DList* header)
{
//首节点
DNode *pos = header->next;

printf("show:");
//首尾相连
while (pos != header) {
printf("%d ", pos->val);
pos = pos->next; //遍历至下一个节点
}

printf("\\n");
}

6.删除一个元素

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

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);
}
}

测试案例

void test04()
{
DList stu_table;
//初始化表
initDList(&stu_table);
//循环头插
for (int i = 0;i < 5;++i) {
insertDListHeader(&stu_table, i + 10);
}
//尾插
insertDListRear(&stu_table, 520);
//展示表中节点
showDList(&stu_table);
printf("====================\\n");

//删除指定节点
delDlist(&stu_table, 10);

//展示表中节点
showDList(&stu_table);
printf("num %d\\n", stu_table.val);

//释放整个表 头置空
releaseDList(&stu_table);
}

main函数

int main()
{
test04();
return 0;
}

输出结果

show:14 13 12 11 10 520
====================
show:14 13 12 11 520
num 5
list num: 0

2.带头指针的双向循环链表

​ 经过上面的带头节点的双向循环链表的理解 这个可以说非常简单了 ​ 我们可以延用在 单链表 中所讲的(具体参考主页数据结构专栏) 最万金油的思路

​ 引入辅助节点，充当头节点

​ 嘻嘻嘻嘻 双向循环链表部分到此结束😆😆

​ (有错误欢迎指出) (疑问也是)❤️❤️😍😍💖💖

至此 链表章节结束 持续更新中… …

l