【初阶数据结构篇】双向链表的实现（赋源码）

🕗 发布于 2024-11-19 10:34 链表 数据结构 双向链表 c++

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

前言

双向链表与单链表实现的思想（思路）基本一致，甚至更简单。

双向链表的实现

1. 双向链表初始化、打印及销毁

1.1 双向链表的初始化

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

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

不传地址：为了保持接口一致性，采用一级指针。

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

1.2 双向链表的打印

打印跟单链表打印大同小异，唯一不同的就是循环结束条件不同，因为双向链表有一个头节点，它不保存有效数据，而是用来放哨（哨兵位）

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

1.3 双向链表的销毁

。和单链表一样

。最后记得销毁哨兵位

//销毁链表
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;
}

2. 双向链表的增加数据不同操作

2.1 双向链表头插

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

2.2 双向链表尾插

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

2.3 双向链表在指定位置之前插入数据

//在指定位置之前插入数据
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;
}

2.4 双向链表在指定位置之后插入数据

//在指定位置之后插入数据
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;
}

3. 双向链表删除数据（不同行为实现方法）

3.1 判空

删除之后不能忘了判空，所以要提前实现一个接口以便判空

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

3.2 双向链表的头删

//头删
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;
}

3.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;

}

3.4 在指定的位置删除数据

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

4. 双向链表查找制定节点数据

4.1 双向链表查找指定位置节点

//查找
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;
}

5（赋源码）

List.h

#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();

list.c

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

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置为NULL
plist = NULL;
Print(plist);
}
int main()
{
ListTest01();
return 0;
}

6.链表与顺序表比较

顺序表对访问数据很高效，而链表相对来将差点。

相信通过这篇文章你对数据结构（双向链表）的有了初步的了解。如果此篇文章对你学习数据结构与算法有帮助，期待你的三连，你的支持就是我创作的动力！！！

下一篇文章再会！！！

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3piibi9t9hc0g

原文地址：https://blog.csdn.net/braveact/article/details/143866815

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：云原生周刊：Kubernetes v1.32 要来了
下一篇：梯度提升树（Gradient Boosting Trees）详解

【MySQL实战45讲笔记】基础篇——事务隔离
简单来说，**事务就是要保证一组数据库操作，要么全部成功，要么全部失败**。在 MySQL 中，事务支持是在**引擎层**实现的。但并不是所有的存储引擎都支持事务，比如MySQL 原生的 MyISAM
阅读更多2024-11-23
MySQL之索引与事务
介绍了MySQL索引的分类，索引的底层数据结构，聚簇索引与非聚簇索引，非聚簇索引导致的回表，索引失效的场景。介绍了事务的特性，事务的隔离级别。
阅读更多2024-11-23
15天大厂真题带刷day1
小美对偶数因子很感兴趣，她将进行 𝑇T 次询问，每次都会给出一个正整数 𝑥x，请你告诉她 𝑥x 是否存在至少一个偶数因子。在一行上输入一个整数 𝑥 (1≤𝑥≤109)x (1≤x≤109) 代表小美询
阅读更多2024-11-23
Fakelocation Server服务器/专业版 Windows11
任务一打开 PowerShell（以管理员身份）命令安装 Chocolatey。任务三打开Fakelocation开源文件 | 查看IP地址。任务四写入Hosts地址文件。任务二可能遇到的错误
阅读更多2024-11-23
Elasticsearch客户端在和集群连接时，如何选择特定的节点执行请求的？
Elasticsearch客户端在和集群连接时，如何选择特定的节点执行请求的？
阅读更多2024-11-23
muduo库的使用
muduo库的使用及其基本原理
阅读更多2024-11-23
Node基本使用
Node基本使用
阅读更多2024-11-23
11 —— 打包模式的应用
需求：在开发模式下想让webpack使用style-loader进行css样式的处理；让它把css代码内嵌在js中；在生产模式下提取css代码。mini-css-extract-plugin插件：提取
阅读更多2024-11-23
04_HDMI20协议解析_General_Control
当通过HDMI传输音频信号时，General_Control是必须要传输的数据包之一, 如果没有，可能会有部分显示器有兼容性问题；General_Control 可以打开或者关闭静音功能；
阅读更多2024-11-23
本地安装YAPI
项目中用到很多的RESTAPI，光靠人工管理或者普通文档肯定是不行的，翻了很多的RESTAPI管理工具，还是选择了YAPI，原因有2，一个是接口位于内网，外网网站上管理测试不到内网接口，另外一个是使用
阅读更多2024-11-23