当前位置： 首页 > news >正文

双向链表的实现

news 2025/5/16 13:12:57

前言

上节谈到单链表的实现，双向链表看似复杂，实际上只需套用单链表的实现，再让各个节点互相连

接即可，以下是具体实现与讲解。

相关接口如下：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//打印链表
void Print(LTNode*);
//初始化
void LTInit(LTNode**);//插入数据
void LTPushBack(LTNode*,LTDataType);
void LTPushFront(LTNode*,LTDataType);//删除
//判空
bool LTEmpty(LTNode*);void LTPopBack(LTNode*);
void LTPopFront(LTNode*);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在指定位置之前或之后插入节点
void LTInsert(LTNode* pos, LTDataType x);
void LTInsertBefore(LTNode* pos, LTDataType x);//删除指定位置的节点
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode**);//为了保持接口的一致性,优化代码
//将初始化和销毁函数传递的参数统一为一级指针
void LTDestroy2(LTNode*);
LTNode* LTInit2();

分析：

1. 首先定义链表结构，与单链表的单向连接不同，双链表需要两个指针来分别存储前后节点的地址。

2.我们把数据类型重定义为LTDataType，便于后续数据类型的修改。

例如，如果要把int类型的双链表改为char类型的双链表，只需要在重定义处将int改为char即可。

3.每一个接口在实现完成之后都要逐个测试！避免后续可能出现的大量报错！

test.c测试代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void ListTest01()
{//LTNode* plist = NULL;//LTInit(&plist);//初始化,只有一个哨兵位,为空链表//保持接口一致性使用一级指针LTNode* plist = LTInit2();//测验尾插LTPushBack(plist, 4);//LTPushBack(plist, 3);//LTPushBack(plist, 4);//LTPushBack(plist, 5);//测验头插LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);//LTNode* pos=LTFind(plist, 2);//if (pos == NULL)
//	printf("没有找到\n");
//else
//	printf("找到了\n");//在指定位置之后插入数据;//LTInsert(pos, 6);//在指定位置之前插入数据//LTInsertBefore(pos, 7);//删除指定位置数据//LTErase(pos);//测验尾删//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);// 测验头删//LTPopFront(plist);//LTPopFront(plist);//LTPopFront(plist);//LTPopFront(plist);//LTPopFront(plist);//LTDestroy(&plist);//保持接口一致性使用一级指针LTDestroy2(plist);//记得把plist置为NULLplist = NULL;Print(plist);
}
int main()
{ListTest01();return 0;
}

一. 双向链表的初始化与销毁

在进入正题之前，我们首先介绍一下上节提到的哨兵位。

哨兵位

我们在创建链表的时候首先需要做的自然是链表的初始化，可是空链表这种情况该怎么办呢？如果

通过开辟节点的方式再置为空，似乎又与“空”一字相悖。

定义

哨兵位就是针对这种情况而诞生，我们开辟一个节点，但是他并不参与数据的存储，而是像哨兵一

样，充当链表的先驱节点，极大方便了后续的种种操作。

创建节点

LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}

分析：

1.与单链表的实现类似，我们定义一个专门用来创建节点的函数来进行每一次的动态开辟操作。

2.在该函数中，我们创建的节点，其next与prev指针均指向本身。

初始化

void LTInit(LTNode** pphead)
{//创建头结点(哨兵位)*pphead = LTBuyNode(-1);
}

分析：

1. 双向链表的头结点只是拿来保存第一个节点的地址的，不用来存储有效数据，双向链表为空的时候就是只有头结点，所以双向链表初始化就是申请一个头结点，并让plist指向头结点即可。

2.为了保持接口的一致性，我们最好采用一级指针的方式进行，通过函数的返回值即可访问到新节点。

LTNode* LTInit2()
{return LTBuyNode(-1);
}

打印

void Print(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}//形成闭环
}

分析：

1.与单链表的直接遍历至尾节点不同，双向链表具有循环特性，各个节点依次连接形成闭环。

2.当节点向后遍历至最初的初始位置时，即代表刚好完整遍历一遍。

销毁

//销毁链表
void LTDestroy(LTNode** pphead)
{assert(pphead&&*pphead);LTNode* pcur, * next;pcur = (*pphead)->next;while (pcur != *pphead){next = pcur->next;free(pcur);pcur = next;}//销毁头结点free(*pphead);*pphead = NULL;pcur = NULL;
}

分析：

1.与单链表类似，需要逐个释放

2.注意最后销毁哨兵位！否则会造成内存泄漏！

3.与初始化类似，为了保持接口一致性，我们采用一级指针进行销毁。

void LTDestroy2(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead=pcur = NULL;
}

注意：在主函数中调用该函数时，需要再手动把哨兵位置为空！

二. 双向链表的插入

核心：

1.创建新节点存储数据

2.修改创建位置处前后节点的next和prev指针

头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}

在指定位置之前插入数据

//在指定位置之前插入数据
void LTInsertBefore(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev = newnode;newnode->prev->next = newnode;
}

在指定位置之后插入数据

//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;//pos->next = newnode;//newnode->next->prev = newnode;pos->next->prev = newnode;pos->next = newnode;
}

三. 双向链表的删除

判空

删除的前提是链表内还有数据可以存储，因此如果链表内仅有一个哨兵位，即为空链表，此时不可

再进行删除。

//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

头删

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

分析：

1. 在判空完成之后，首先定义一个指针del来指向将要删除的节点

2. 再修改删除节点下一个节点的前驱指针

3. 修改头节点的后驱指针

尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->prev;phead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;}

与头删同理。

在指定位置删除数据

//删除指定位置节点
void LTErase(LTNode* pos)
{LTNode* del = pos;del->prev->next = pos->next;del->next->prev = del->prev;free(pos);pos = NULL;
}

直接遍历查找，找到删除节点后原理同上。

四. 双向链表查找指定数据

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

分析：

1.直接遍历查找即可，注意循环条件

2.找到则返回节点地址，未找到则返回空

五. 顺序表与链表的比较

六. 完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//打印链表
void Print(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}
}//申请新节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//初始化链表
void LTInit(LTNode** pphead)
{//创建头结点(哨兵位)*pphead = LTBuyNode(-1);
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->prev;phead->prev = del->prev;del->prev->next = phead;free(del);del = NULL;}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;//pos->next = newnode;//newnode->next->prev = newnode;pos->next->prev = newnode;pos->next = newnode;
}//在指定位置之前插入数据
void LTInsertBefore(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev = newnode;newnode->prev->next = newnode;
}//删除指定位置节点
void LTErase(LTNode* pos)
{LTNode* del = pos;del->prev->next = pos->next;del->next->prev = del->prev;free(pos);pos = NULL;
}//销毁链表
void LTDestroy(LTNode** pphead)
{assert(pphead&&*pphead);LTNode* pcur, * next;pcur = (*pphead)->next;while (pcur != *pphead){next = pcur->next;free(pcur);pcur = next;}//销毁头结点free(*pphead);*pphead = NULL;pcur = NULL;
}void LTDestroy2(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead=pcur = NULL;
}LTNode* LTInit2()
{return LTBuyNode(-1);
}

小结：本文主要介绍了双向链表的结构，概念，相关接口的具体实现方法和链表与顺序表的区别，

并简要介绍了哨兵位的含义与作用，欢迎各位大佬前来斧正支持！！！


http://www.mrgr.cn/news/38368.html

相关文章：

  • 为什么说AI普及之路还存在挑战呢？
  • 参数高效的迁移学习在自然语言处理中的应用
  • mov视频怎么转换成mp4？这几种转换方法值得收藏起来！
  • C++里的随机数
  • CentOS 修改服务器登录密码的完整指南
  • 【C语言】动态内存管理：malloc、calloc、realloc、free
  • vue3使用Teleport 控制台报警告：Invalid Teleport target on mount: null (object)
  • c++进阶学习--------多态
  • Java如何在方法中操作数组元素
  • 计算机网络各层有哪些协议？计算机网络协议解析：从拟定到实现，全面了解各层协议的作用与区别
  • 业务资源管理模式语言19
  • 05-成神之路_ambari_Ambari实战-013-代码生命周期-metainfo-configFiles详解
  • 关系型数据库的特点
  • 工控主板在工业控制中扮演什么角色
  • k8s基于nfs创建storageClass
  • 【2023工业3D异常检测文献】PointCore: 基于局部-全局特征的高效无监督点云异常检测器
  • 2024年7月大众点评温州美食店铺基础信息
  • 综合业务区的数字化创新与智能化蓝图
  • 天龙八部怀旧单机微改人面桃花+安装教程+GM工具+虚拟机一键端
  • 【MyBatis】【Java】数据库连接之URL怎么写