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

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

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

⚙️操作环境:Visual Studio 2022

目录

一、什么是双链表？

二、双链表温习

1. 双链表的结构

2. 基本操作

3. 双链表讲解说明

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

1. 头文件

2. 函数源文件

3. 测试代码用例

4. 小结

四、总结

共勉

一、什么是双链表？

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

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

二、深入认识双链表

1. 双链表的结构

<code>在C语言中，双链表可以通过结构体来定义。一个典型的双链表节点结构如下：

typedef struct Node {

int data; // 存储数据

struct Node *prev; // 指向前一个节点

struct Node *next; // 指向下一个节点

} Node;

2. 基本操作

对于双链表，我们通常需要实现以下几种基本操作：

创建空链表插入节点删除节点遍历链表查找节点获取链表长度清空链表

3. 双链表讲解说明

本篇文章主要讲解的是带头双向循环链表。

带头双向循环链表：

结构最复杂

，一般用在单独存储数据。实际中使用的链表数据结构，都是带双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。（前提是

【C语言】最详细的单链表（两遍包会！）-CSDN博客

可以手拿把掐哦！）

三、代码示例（链表 · 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 不是 NULL

DLL* 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); // 在第二个节点之后插入25

printf("在第二个元素后插入 25 后的列表：\n");

print(list);

// 再次检查链表是否为空

printf("列表是空的吗？ %s\n", empty(list) ? "Yes" : "No");

// 销毁链表（注意：实际代码中应实现销毁函数）

// destroy_list(list); // 假设实现了这个函数

return 0;

}

4. 小结

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

四、总结

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

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

共勉