【C语言】双链表

🦄个人主页:小米里的大麦-CSDN博客

🎏所属专栏:C语言数据结构_小米里的大麦的博客-CSDN博客

🎁代码托管:黄灿灿/数据结构 (gitee.com)

⚙️操作环境:Visual Studio 2022

目录

一、什么是双链表？

二、双链表温习

1. 双链表的结构

2. 基本操作

3. 双链表讲解说明

三、代码示例（链表 · 59b38b6 · 黄灿灿/数据结构 - Gitee.com）

1. 头文件

2. 函数源文件

3. 测试代码用例

4. 小结

四、总结

共勉

---

一、什么是双链表？

在数据结构中，链表是一种线性数据结构，其中元素不是在内存中连续存储的，而是通过指针链接在一起。双链表是链表的一种形式，每个节点包含三个部分：一个数据字段和两个指针字段，分别指向其前驱节点和后继节点。这种结构允许从任意方向遍历链表。

如果提前脑海里有一定的双链表形式/样例，一定会大大帮助我们进行理解，毕竟数据结构的核心思想是图，是画图！所以，不妨看看这个：双链表 数据结构与算法c语言，完整代码动画版_哔哩哔哩_bilibili.（有一定的认识就不需要啦！）

二、深入认识双链表

1. 双链表的结构

在C语言中，双链表可以通过结构体来定义。一个典型的双链表节点结构如下：
typedef struct Node {int data; // 存储数据struct Node *prev; // 指向前一个节点struct Node *next; // 指向下一个节点
} Node;

3. 双链表讲解说明

三、代码示例（链表 · 59b38b6 · 黄灿灿/数据结构 - Gitee.com）

虽然双链表的结构相比单链表更复杂了，但正是由于双链表很“对称”，有规律，所以实现起来更方便了。

1. 头文件

#pragma once
//Double linked list：双链表#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>typedef struct Double_linked_list
{struct Double_linked_list* prev;int data;struct Double_linked_list* next;
}DLL;//创建一个新的节点：Create a new node
DLL* Cnew_node(int x);//初始化空的双向循环链表，返回指向头结点的指针，initialize：初始化
DLL* init_list();//打印链表内容
void print(DLL* phead);//检查链表是否为空:Check if the linked list is empty
bool empty(DLL* phead);//尾插：Tail plugging
void tail_plug(DLL* phead, int x);//头插：Header
void header(DLL* phead, int x);//在给定的位置 pos 插入一个包含 x 的新节点:Insert a new node containing x at the given location pos
void insert(DLL* pos, int x);

2. 函数源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "Double linked list.h"//Double linked list：双链表//创建一个新的节点：Create a new node
DLL* Cnew_node(int x)
{DLL* newnode = (DLL*)malloc(sizeof(DLL));if (newnode == NULL){perror("malloc fail");//exit(-1);//如果分配内存失败，则终止程序}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}//初始化空的双向循环链表，返回指向头结点的指针，initialize：初始化
DLL* init_list()
{DLL* phead = Cnew_node(-1);phead->next = phead;phead->prev = phead;return phead;
}//打印链表内容
void print(DLL* phead)
{assert(phead);printf("<->head<->");DLL* temp = phead->next;while (temp != phead){printf("%d<->", temp->data);temp = temp->next;}printf("\n");
}//检查链表是否为空:Check if the linked list is empty
bool empty(DLL* phead)
{assert(phead);return phead->next == phead;
}//尾插：Tail plugging
void tail_plug(DLL* phead, int x)
{assert(phead);insert(phead, x);
}//头插：Header
void header(DLL* phead, int x)
{assert(phead);insert(phead->next, x);
}//在给定的位置 pos 插入一个包含 x 的新节点:Insert a new node containing x at the given location pos
void insert(DLL* pos, int x)
{assert(pos); // 确保 pos 不是 NULLDLL* prev = pos->prev; // 获取 pos 节点的前一个节点DLL* newnode = Cnew_node(x); // 创建一个包含数据 x 的新节点// 更新 prev 节点的 next 指针，使其指向新节点prev->next = newnode;// 设置新节点的 prev 指针，使其指向 prev 节点newnode->prev = prev;// 设置新节点的 next 指针，使其指向 pos 节点newnode->next = pos;// 更新 pos 节点的 prev 指针，使其指向新节点pos->prev = newnode;
}

3. 测试代码用例

#define _CRT_SECURE_NO_WARNINGS 1
#include "Double linked list.h"//Double linked list：双链表int main() {// 初始化链表DLL* list = init_list();// 测试空链表检查printf("列表是空的吗？ %s\n", empty(list) ? "Yes" : "No");// 测试头插header(list, 10);header(list, 20);header(list, 30);// 打印链表内容printf("头部插入后的列表：\n");print(list);// 测试尾插tail_plug(list, 40);tail_plug(list, 50);tail_plug(list, 60);// 打印链表内容printf("尾部插入后的列表：\n");print(list);// 测试插入到指定位置insert(list->next->next, 25); // 在第二个节点之后插入25printf("在第二个元素后插入 25 后的列表：\n");print(list);// 再次检查链表是否为空printf("列表是空的吗？ %s\n", empty(list) ? "Yes" : "No");// 销毁链表（注意：实际代码中应实现销毁函数）// destroy_list(list); // 假设实现了这个函数return 0;
}

4. 小结

当你看到这里的时候就会发现：双链表代码比单链表的代码会短很多，而且双链表最主要的其实就是那个插入函数，如果对上述有注释的代码还存在疑惑，不妨画一画图，会极大方便我们进行理解！如果是一头雾水，那基本上是单链表不过关，可以再回去研究研究：【C语言】最详细的单链表（两遍包会！）-CSDN博客

四、总结

在这篇文章中，我们介绍了双链表的基本概念，并展示了如何使用C语言来创建和操作双链表。双链表相比于单链表提供了更多的灵活性，因为我们可以轻松地向前或向后移动。然而，这种额外的功能也带来了更高的存储开销，因为每个节点都需要额外的指针来保存前驱节点的信息。

以上就是关于C语言中双链表的介绍，希望对你有所帮助！

共勉