【数据结构】双向链表的C语言实现--万字详解介绍
迪丽瓦拉
2025-05-30 14:54:37
0次

​在这里插入图片描述

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

文章目录

  • 1.双向链表
    • 1.1 双向链表的概念：
  • 2.双向链表的实现
    • 2.1 结构设计
    • 2.2 接口总览
    • 2.3 初始化
    • 2.4 创建新节点
    • 2.5 尾插
    • 2.6 头插
    • 2.7 尾删
    • 2.8 头删
    • 2.9 查找
    • 2.10 在pos位置之前插入
    • 2.11 在pos位置删除
    • 2.12 打印
    • 2.13 销毁
    • 2.14 判断是否为空
  • 3. 完整代码
    • 3.1 List.h
    • 3.2 List.c
    • 3.3 test.c
  • 4.总结：

1.双向链表

由于单链表也就是单向无头非循环链表，是一个有缺陷的结构 ，它有时会作为其他数据结构的子结构 。比如在尾插时，需要找到尾结点；尾删时，需要找到尾结点的前一个节点；在任意位置删除时需要找到该位置前一个节点等，这些都需要用时间复杂度为 O(N)的算法来处理。基于单链表的这些缺陷，带头双向循环链表，也就是我们说的双向链表就完美的解决了这些问题

1.1 双向链表的概念：

双向链表实际上就是带头双向循环链表
链表的几种结构：带头 / 不带头，单向 / 双向，循环 / 非循环，而双向链表很明显就是这些结构中最复杂结构的
特点：1.含有头结点 —— 有一个不存储有效数据的虚拟节点，链表永不为空，所以无需传二级指针，只需要改变节点之间的链接关系2.双向—— 可以通过一个节点直接找到上一个节点3.循环 —— 链表头尾相连呈环状，链表中无空指针。

它的结构设计有些特殊，由于是双向，所以要比单链表多一个prev用来找到上一个节点。同样的 单链表 有的next、data 也必不可少；它的循环结构，需要最后一个节点的 next 能找到第一个节点，第一个节点的 prev 能找到最后一个节点。

请添加图片描述
从这幅图就可以看出，双向链表的结构,解决了单链表插入、删除数据时复杂的操作，加上存储单元之间的链接多样，让数据之间的管理变得简单

2.双向链表的实现

2.1 结构设计

双向链表 比 单链表 的结构多一个prev指针，用来记录上一个节点的地址。

typedef struct ListNode
{LTDataType data; // 保存数据struct ListNode* next; // 记录下一个节点的地址struct ListNode* prev; // 记录上一个节点的地址
}LTNode;

2.2 接口总览

双向链表总共需要以下接口：

// 初始化
LTNode* ListInit(); // 使用返回值处理
// 打印
void ListPrint(LTNode* phead);
// 尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 尾删
void ListPopBack(LTNode* phead);
// 头插
void ListPushFront(LTNode* phead, LTDataType x);
// 头删
void ListPopFront(LTNode* phead);
// 查找元素
LTNode* ListFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(LTNode* pos);
// 销毁双向链表
void ListDestroy(LTNode* phead);

虽然接口和单链表差不多，但是这些接口的实现，远远比单链表简单
而且这里有一个特殊的地方就是函数传参时，初始化接口参数 无参 ，其他接口传的是 一级指针 ，为什么？

双向链表是带头的，含有一个头结点，就是我们单链表中提到的 哨兵位 。哨兵位不存储 有效数据 ，存在哨兵位链表不为空，使实现接口时更加方便。

  1. 初始化函数无参。双向链表初始化只需要创建哨兵位，然后得到哨兵位即可。在这里同样可以使用二级指针来操作，但可以不用
  2. 其他接口参数传一级指针，是因为哨兵位不存储有效数据并且我并不需要改变哨兵位，所以我只需要找到哨兵位然后改变它的链接关系就可以，所以不需要二级指针

注意只要存在哨兵位，链表的第一个节点就是哨兵位后面第一个节点

2.3 初始化

创建一个 哨兵位 节点。双向链表 在只有一个哨兵位时，让它自己指向自己。哨兵位的next指向它自己的prev，哨兵位的prev指向它自己的next 。一个特殊的环形链表。由于我们这里使用的是返回值的形式，所以只要创建返回就可以。而之前的单链表是因为结构为无头单向链表，所以不用初始化，直接置空（NULL）足矣。

// 初始化
LTNode* ListInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));// 双向带头循环链表的prev指向next，next指向prev// 但是这里只有一个节点，所以只能让它自己指向自己if (phead == NULL){perror("ListInit");exit(-1);}phead->next = phead;phead->prev = phead;return phead;
}

2.4 创建新节点

当双向链表需要插入元素时，需要创建节点。直接 malloc 开辟，然后把值存入，两个指针给为空指针，然后返回节点就行。

// 创建新节点
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("ListPushBack");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

2.5 尾插

单链表 的尾插，在链表为空时，需要特殊处理；在平常插入时，需要找到尾结点 ，改变尾结点的链接。
对于 双向链表的尾结点，就是哨兵位的prev ，将其拷贝一份，放在 tail 中，然后将 tail 的 next 链接至新节点 newnode ，然后将 newnode 的 prev 链接到 tail。在处理一下 newnode 的 prev 和 tail 的链接就可以了

单链表 要 O(N) 的时间复杂度的尾插，在这里只需要用 O(1) 就可以完成

加粗样式

// 尾插
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);// 有可能为空，传错了参数LTNode* tail = phead->prev;// 尾就是prev，由于是双向循环链表，所以头的prev就是尾LTNode* newnode = BuyListNode(x);// phead              tail            newnodetail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

2.6 头插

对于 头插 来说，首先需要创建节点，然后将哨兵位的后一个节点，即链表实际上的 第一个节点 phead->next，给定一个新节点 newnode 。然后将 newnode 的 prev 链接到 哨兵位。再将 newnode 的 next 给定为先前的第一个节点 next 。然后改变该节点 (next)的 prev 和 newnode 的链接关系。

// 头插
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* next = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;//不能随便换顺序//newnode->next = next;//next->prev = newnode;//	phead->next = newnode;//newnode->prev = phead;}

2.7 尾删

对于双向链表的尾删，只要找到尾结点的前一个节点改变它和哨兵位的连接关系即可。
如果要找到尾结点的前一个节点，那么只需要通过 哨兵位 的 prev 找到 尾，通过 尾 的 prev 就可以找到 尾结点的前一个节点。然后调整这个节点和哨兵位的链接关系，然后 释放尾结点 就可以了。

注意当链表只有哨兵位的时候不能进行删除

// 尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);// 防止把哨兵位删掉//暴力方法 assert(!LTEmpty(phead));LTNode* tail = phead->prev; LTNode* tailprev = tail->prev;free(tail);tail=NULL;phead->prev = tailprev;tailprev->next = phead;
}

2.8 头删

对于头删，需要删除链表的第一个节点，也就是哨兵位的 next 节点 ，我需要改变哨兵位和第二个节点的链接关系，然后释放 第一个节点 。

void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* next = phead->next;LTNode* nextNext = next->next;phead->next = nextNext;nextNext->prev = phead;free(next);tail=NULL;
}

2.9 查找

对于查找一个元素在 双向链表 中存不存在，采用遍历链表的形式。但是对于 双向链表 来说，它是没有指向 NULL 的节点的，它是一个环，停不下来。所以我们要把循截止条件设定为 != phead ，这个条件就表示，已经遍历过一遍链表了，走到哨兵位了。
如果找到，返回该节点的地址；如果找不到返回 NULL 。

// 查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

2.10 在pos位置之前插入

在 pos 位置之前插入，那么通过 pos 的 prev 找到 pos 位置的上一个节点 posPrev ，然后改变 posPrev 和 新节点 newnode 之间的链接和 newnode 和 pos 之间的链接。和头插尾插思路大致相同。

// 在pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}

有了这个接口，就可以把它 复用 于 尾插 和 头插。
对于 尾插 来说， pos 位置就是 phead ，因为 phead 的前面就是链表的尾，在 phead 位置前插入，就是尾插：

void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
}

对于 头插 来说，pos 位置就是 phead->next ，为第一个节点的前面，在 phead->next 位置前插入，就是头插：

void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead->next, x);
}

2.11 在pos位置删除

在 pos 位置删除，只要找到 pos 的前一个节点 posPrev ，然后找到 pos 的后一个节点 posNext ，然后将这两个节点的 prev 和 next 建立正确的链接关系。然后释放 pos 节点，pos 节点置空。
注意删除的位置不能是哨兵位。
由于这里设计的原因，再传 phead 就显得有点不划算了，所以我们需要注意一下，pos 不能为哨兵位。

void ListErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;
}

同样的，这个接口也能复用于 尾删 和 头删 。
对于尾删 来说，pos 位置就是 phead->prev ，为链表的尾，删除 phead->prev 位置，就是尾删：

void ListPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);// 防止把哨兵位删掉 ListErase(phead->prev);
}

对于头删来说，pos 位置就是 phead->next ，为链表的头，删除 phead->next 位置，就是头删：

// 头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);// 防止把哨兵位删掉 ListErase(phead->next);
}

2.12 打印

打印整个链表，只需要遍历链表，控制好循环停止条件：

// 打印
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}

2.13 销毁

需要把 哨兵位 ，链表的节点全部删除，那么我就要使用循环来删除。所以，销毁双向链表的思路和查找是差不多的，循环的结束条件为!= phead。在销毁的过程中，每次记住我当前节点的下一个节点，以便迭代。
注意哨兵位是不能正常删除的，由于在函数中，我释放了哨兵位，并要将其置空。释放是可以的，因为我知道哨兵位的地址，释放就可以，但是置空却完成不了。因为我的哨兵位是形参，改变形参并不能影响实参，所以我们还需要在主函数中将哨兵位置空

// 销毁
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);// 只销毁了形参，没有销毁实参，这里只是象征性的销毁一下phead = NULL;
}

2.14 判断是否为空

//
bool LTEmpty(LTNode* phead)
{return phead->next==phead;

3. 完整代码

3.1 List.h

#pragma once
/*
* c++中带头双向循环链表命名方式为List，所以我们也采用这个命名方式
*/
#include 
#include 
#include 
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;
// 初始化
LTNode* ListInit();// 使用返回值处理
// 打印
void ListPrint(LTNode* phead);
// 尾插
void ListPushBack(LTNode* phead, LTDataType x);
// 尾删
void ListPopBack(LTNode* phead);
// 头插
void ListPushFront(LTNode* phead, LTDataType x);
// 头删
void ListPopFront(LTNode* phead);
// 查找元素
LTNode* ListFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(LTNode* pos);
// 销毁双向链表
void ListDestroy(LTNode* phead);

3.2 List.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "List.h"
// 初始化
LTNode* ListInit()
{LTNode* phead = (LTNode*)malloc(sizeof(LTNode));// 双向带头循环链表的prev指向next，next指向prev// 但是这里只有一个节点，所以只能让它自己指向自己if (phead == NULL){perror("ListInit");exit(-1);}phead->next = phead;phead->prev = phead;	return phead;
}
// 创建新节点
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("ListPushBack");exit(-1);}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
// 打印
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}// 尾插
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);// 一定不为空-->有哨兵位//LTNode* tail = phead->prev;// 尾就是prev，由于是双向循环链表，所以头的prev就是尾//LTNode* newnode = BuyListNode(x);//phead              tail            newnode//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead;//phead->prev = newnode;ListInsert(phead, x);
}// 尾删
void ListPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);// 防止把哨兵位删掉 /*LTNode* tail = phead->prev; LTNode* tailprev = tail->prev;free(tail);phead->prev = tailprev;tailprev->next = phead;*/ListErase(phead->prev);
}// 另一种写法
//void ListPopBack(LTNode* phead)
//{
//	assert(phead);
//	assert(phead->next != phead);// 防止把哨兵位删掉 
//	LTNode* tail = phead->prev; 
//	
//	phead->prev = tail->prev;
//	tail->prev->next = phead;
//	
//	free(tail); 	
//}// 头插
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);/*LTNode* newnode = BuyListNode(x);LTNode* next = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;*/ListInsert(phead->next, x);
}// 头删
void ListPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);/*LTNode* next = phead->next;LTNode* nextNext = next->next;phead->next = nextNext;nextNext->prev = phead;free(next);*/ListErase(phead->next);
}// 查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}// 在pos位置之前插入
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}// 在pos位置删除
void ListErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;
}// 销毁
void ListDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);// 只销毁了形参，没有销毁实参phead = NULL;
}

3.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "List.h"
// 测试尾插、尾删void TestList1()
{LTNode* plist = ListInit();// 哨兵位ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);// 双向链表的缺点// 当链表只剩下哨兵位时，链表为空// 如果这时候进行删除，会把哨兵位删掉  // ListPopBack(plist);ListPrint(plist);
}
// 测试头插、任意位置删除
void TestList2()
{LTNode* plist = ListInit();// 哨兵位ListPushFront(plist, 1);ListPushFront(plist, 2);ListPushFront(plist, 3);ListPushFront(plist, 4);ListPushFront(plist, 5);ListPrint(plist);ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPrint(plist);LTNode* pos = ListFind(plist, 2);if (pos){ListErase(pos);}ListPrint(plist);ListDestroy(plist);plist = NULL;// 手动置空
}int main()
{//TestList1();TestList2();return 0;
}

4.总结：

今天我们认识并学习了带头双向循环链表的相关概念、结构与接口实现，并且针对每个常用的功能接口进行了实现。总体来说，双向链表的结构是非常完美的，一般我们说的存储数据的链表其实也就是双向链表，单链表一般是作为其他数据结构的子结构的。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~

在这里插入图片描述

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Linux下字符设备驱动开发以及流程介绍

下一篇：Spring Boot/Cloud集成Sentinel详解@SentinelResource埋点 | Spring Cloud 26

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作： 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统（六）：学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤： 在Student.cpp的...
A.机器学习入门算法（三）：基... 机器学习算法（三）：K近邻(k-nearest neigh...
数字温湿度传感器DHT11模块... 模块实例https://blog.csdn.net/qq_38393591/article/deta...
有限元三角形单元的等效节点力 文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
Redis 所有支持的数据结构... Redis 是一种开源的基于键值对存储的 NoSQL 数据库，支持多种数据结构。以下是...
win下pytorch安装—c... 安装目录一、cuda安装1.1、cuda版本选择1.2、下载安装二、cudnn安装三、pytorch...
MySQL基础-多表查询 文章目录MySQL基础-多表查询一、案例及引入1、基础概念2、笛卡尔积的理解二、多表查询的分类1、等...
keil调试专题篇 调试的前提是需要连接调试器比如STLINK。 然后点击菜单或者快捷图标均可进入调试模式。 如果前面...
MATLAB | 全网最详细网... 一篇超超超长，超超超全面网络图绘制教程，本篇基本能讲清楚所有绘制要点&#...
IHome主页 - 让你的浏览... 随着互联网的发展，人们越来越离不开浏览器了。每天上班、学习、娱乐，浏览器...
TCP 协议 一、TCP 协议概念 TCP即传输控制协议（Transmission Control ...
营业执照的经营范围有哪些 营业执照的经营范围有哪些 经营范围是指企业可以从事的生产经营与服务项目，是进行公司注册...
C++ 可变体(variant... 一、可变体(variant) 基础用法 Union的问题： 无法知道当前使用的类型是什...
血压计语音芯片，电子医疗设备声... 语音电子血压计是带有语音提示功能的电子血压计，测量前至测量结果全程语音播报࿰...
MySQL OCP888题解0... 文章目录1、原题1.1、英文原题1.2、答案2、题目解析2.1、题干解析2.2、选项解析3、知识点3...
【2023-Pytorch-检... （肆十二想说的一些话）Yolo这个系列我们已经更新了大概一年的时间，现在基本的流程也走走通了，包含数...
实战项目：保险行业用户分类 这里写目录标题1、项目介绍1.1 行业背景1.2 数据介绍2、代码实现导入数据探索数据处理列标签名异...
记录--我在前端干工地(thr... 这里给大家分享我在网上总结出来的一些知识，希望对大家有所帮助 前段时间接触了Th...
43 openEuler搭建A... 文章目录43 openEuler搭建Apache服务器-配置文件说明和管理模块43.1 配置文件说明...