【数据结构】双向链表

🕗 发布于 2024-07-11 18:27 数据结构 链表

Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
💥💥个人主页：奋斗的小羊
💥💥所属专栏：C语言

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

前言

单链表只能通过某个节点的地址单向的访问数据，而双向链表可以通过某个节点的地址双向的访问数据，增删查改的效率更高，但是代码的实现却比单链表简单，总的来说，双向链表优势更明显一些。

1、链表的分类

链表分为带头的、不带头的，单向的、双向的，循环的、不循环的组合起来一共八种，而我们只学习常见的不带头单向不循环链表和带头双向循环链表，也就是单链表和双向链表。
双向链表：
在这里插入图片描述
其实在上篇文章中我们将单链表的第一个节点称作头节点是不准确的，之所以这么称呼是为了好理解，因为单链表是不带头的，双向链表才有头结点，也称作哨兵位。

双向链表头节点内不存有效数据，存的是无效的数据。
哨兵位是不能改变的，只能改变其指向

2、双向链表的实现

2.1双向链表节点

双向链表的节点需要存数据，还要存前一个和后一个节点的地址，因此双向链表的节点为：

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
dlist_data_type data;
struct dlist* next
struct dlist* prev;
}dlist;

2.2申请节点

不像单链表，双向链表最少得有一个节点，就是头节点，也叫哨兵位。
在增删查改之前，双向链表必须初始化一个哨兵位，哨兵位内存一个无效数据。

申请的节点初始时两个指针指向自己。

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
dlist* newdlist = (dlist*)malloc(sizeof(dlist));
if (newdlist == NULL)
{
perror("malloc fail!");
return 1;
}
newdlist->data = x;
newdlist->next = newdlist;
newdlist->prev = newdlist;
return newdlist;
}

初始化哨兵位有以下两种方法：
以参数的形式返回：

void dlist_init(dlist** pphead)
{
assert(pphead);
*pphead = dlist_buy(-1);
}

这个方法要求使用二级指针。
以返回值的形式返回：

dlist* dlist_init()
{
dlist* phead = dlist_buy(-1);
return phead;
}

这个方法更加简单易理解。

2.3数据的打印和查找

数据的打印和查找跟单链表区别不大，就不再赘述了。
唯一需要注意的是结束循环的条件，当指针指向哨兵位时结束循环，而不是判NULL。

//打印数据
void dlist_print(dlist* phead)
{
assert(phead);
dlist* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}

2.4头插和尾插

与单链表不同的是，双向链表的增删查改操作不会改变哨兵位，因此只需要传值调用就可。
双向链表的插入操作需要对三个节点做修改，在修改的过程中，注意先修改新节点，再修改后一个节点，最后修改前一个节点。

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);

//新尾节点
newdlist->prev = phead->prev;
newdlist->next = phead;

//旧尾节点
phead->prev->next = newdlist;

//头节点（哨兵位）
phead->prev = newdlist;
}
//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);

//新节点
newdlist->prev = phead;
newdlist->next = phead->next;

//旧节点
phead->next->prev = newdlist;

//哨兵位
phead->next = newdlist;
}

2.5头删和尾删

删除操作的前提是不能没有节点（哨兵位不算），在删除前还是先保存节点的地址，将双向链表重新拼接起来后再释放节点。

//尾删
void dlist_pop_back(dlist* phead)
{
assert(phead);
assert(phead->next != phead);//双向链表不能为空
dlist* del = phead->prev;
//新尾节点
del->prev->next = phead;
//哨兵位
phead->prev = del->prev;
free(del);
del = NULL;
}

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

2.6在指定位置插入、删除数据

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
assert(pos);
dlist* newdlist = dlist_buy(x);
newdlist->prev = pos;
newdlist->next = pos->next;

pos->next->prev = newdlist;
pos->next = newdlist;
}
//删除指定位置的节点
void dlist_erase(dlist* pos)
{
assert(pos);
dlist* del = pos;
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = NULL;
}

删除指定位置的数据后，因为这个函数我们用的是传值调用，在释放掉指定位置的节点后，只是把形参指针置NULL，而实参指针依旧指向这个位置，因此在函数调用结束后要给实参指针置NULL。

2.7销毁双向链表

双向链表销毁的结束条件也是当遍历指针指向头节点时跳出循环，最后还要单独释放哨兵位，双向链表的销毁函数调用结束后，也要给指向哨兵位的指针置NULL。

//销毁
void dlist_destroy(dlist* phead)
{
assert(phead);
dlist* pcur = phead->next;
while (pcur != phead)
{
dlist* next = pcur->next;
free(pcur);
pcur = next;
}
free(pcur);
pcur = NULL;
}

3、双向链表完整代码

dlist.h:

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int dlist_data_type;

//双向链表节点
typedef struct dlist
{
dlist_data_type data;
struct dlist* next;
struct dlist* prev;
}dlist;

//初始化
//插入数据之前，双向链表必须初始化到只有一个头节点（哨兵位）
//void dlist_init(dlist** pphead);//以参数的形式返回
dlist* dlist_init();//以返回值的形式返回

//打印数据
void dlist_print(dlist* phead);
//查找
dlist* dlist_find(dlist* phead, dlist_data_type x);
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x);
//头插
void dlist_push_front(dlist* phead, dlist_data_type x);
//尾删
void dlist_pop_back(dlist* phead);
//头删
void dlist_pop_front(dlist* phead);
//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x);
//删除指定位置的节点
void dlist_erase(dlist* pos);
//销毁
void dlist_destroy(dlist* phead);

dlist.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

//申请节点
dlist* dlist_buy(dlist_data_type x)
{
dlist* newdlist = (dlist*)malloc(sizeof(dlist));
if (newdlist == NULL)
{
perror("malloc fail!");
return 1;
}
newdlist->data = x;
newdlist->next = newdlist;
newdlist->prev = newdlist;
return newdlist;
}

//初始化
//void dlist_init(dlist** pphead)
//{
//assert(pphead);
//*pphead = dlist_buy(-1);
//}

dlist* dlist_init()
{
dlist* phead = dlist_buy(-1);
return phead;
}

//打印数据
void dlist_print(dlist* phead)
{
assert(phead);
dlist* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}

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

//插入操作不改变哨兵位，因此传一级指针即可
//尾插
void dlist_push_back(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);

//新尾节点
newdlist->prev = phead->prev;
newdlist->next = phead;

//旧尾节点
phead->prev->next = newdlist;

//头节点（哨兵位）
phead->prev = newdlist;
}

//头插
void dlist_push_front(dlist* phead, dlist_data_type x)
{
assert(phead);
dlist* newdlist = dlist_buy(x);

//新节点
newdlist->prev = phead;
newdlist->next = phead->next;

//旧节点
phead->next->prev = newdlist;

//哨兵位
phead->next = newdlist;
}

//尾删
void dlist_pop_back(dlist* phead)
{
assert(phead);
assert(phead->next != phead);//双向链表不能为空
dlist* del = phead->prev;
//新尾节点
del->prev->next = phead;
//哨兵位
phead->prev = del->prev;
free(del);
del = NULL;
}

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

//在指定位置之后插入数据
void dlist_insert_back(dlist* pos, dlist_data_type x)
{
assert(pos);
dlist* newdlist = dlist_buy(x);
newdlist->prev = pos;
newdlist->next = pos->next;

pos->next->prev = newdlist;
pos->next = newdlist;
}

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

//销毁
void dlist_destroy(dlist* phead)
{
assert(phead);
dlist* pcur = phead->next;
while (pcur != phead)
{
dlist* next = pcur->next;
free(pcur);
pcur = next;
}
free(pcur);
pcur = NULL;
}

test.c:

#define  _CRT_SECURE_NO_WARNINGS

#include "dlist.h"

void test()
{
//dlist* plist = NULL;
//dlist_init(&plist);

dlist* plist = dlist_init();

//尾插
dlist_push_back(plist, 1);
dlist_push_back(plist, 2);
dlist_push_back(plist, 3);
dlist_print(plist);

//头插
//dlist_push_front(plist, 1);
//dlist_push_front(plist, 2);
//dlist_push_front(plist, 3);
//dlist_print(plist);

//尾删
//dlist_pop_back(plist);
//dlist_pop_back(plist);
//dlist_pop_back(plist);
//dlist_print(plist);

//头删
//dlist_pop_front(plist);
//dlist_print(plist);
//dlist_pop_front(plist);
//dlist_print(plist);
//dlist_pop_front(plist);
//dlist_print(plist);

//dlist* find = dlist_find(plist, 2);
//dlist_insert_back(find, 4);
//dlist_print(plist);

//dlist* find = dlist_find(plist, 2);
//dlist_erase(find);
//find = NULL;
//dlist_print(plist);

dlist_destroy(plist);
plist = NULL;//手动置空
}

int main()
{
test();
return 0;
}

4、顺序表和链表比较

	顺序表	链表（双向链表）
存储空间上	逻辑、物理上都连续	逻辑上连续、物理上不一定连续
随机访问	复杂度O(1)	复杂度O(N)
任意位置插入或删除数据	需要挪动数据，复杂度O(N)	只需要改变指针指向
插入	动态顺序表，空间不够时扩容，扩容本身就有消耗，还容易空间浪费	没有容量的概念
应用场景	数据高效存储+频繁访问	任意位置频繁插入、删除数据
缓存利用率	高	低

顺序表和链表优势互补，在不同的应用场景下能发挥各自的优势。

总结

如果应用场景中需要频繁进行查找和删除操作，并且能够接受更多的内存消耗，双向链表可能更加合适。
如果内存比较有限或者对查找和删除操作的效率要求不高，单链表可能更适合.

原文地址：https://blog.csdn.net/2301_78843337/article/details/140350228

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

上一篇：Zabbix Sia Zabbix 逻辑漏洞（CVE-2022-23134）
下一篇：c++初阶学习----入门（下）

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30