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

【数据结构】双向链表

news 2025/5/14 7:07:20

本文是小编巩固自身而作，如有错误，欢迎指出！

1.双向链表的概念

双向链表一般指的是双向带头循环链表。

其中的双向指的就是这个链表不如单链表一般只能按顺序进行访问，同时可以反向访问，

循环就是如之前的环装链表一般可以从尾节点重新回到头结点，

带头就需要注意，此处的头不是之前的头节点，是最后一个节点后，第一个节点前的节点，其中不储存所需数据，仅仅用于“放哨”，因此也常常被称作哨兵节点。

一个双向链表大概可以画成以下的图 

2.双向链表的实现 

2.1双向链表的结构声明

如上图所示，一个节点具有3个部分，其中作用分别是

1.储存上一个节点的地址。

2.储存下一个节点的地址。

3.储存数据。

typedef int ltdatatype;
struct Listnode {ltdatatype  data;struct Listnode* next;struct Listnode* prev;
};
typedef struct Listnode LTNode;

 2.2创造新的节点

 在创建一个独立节点时，其一开始自己就是一个独立链表，所以他的prev和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;
}

2.3双向链表的初始化 

即创造一个“哨兵”位，在此例中我们将其值置为-1

//双向链表的初始化
LTNode* ltinit()
{LTNode* phead = ltbuynode(-1);return phead;
}

2.4双向链表的尾插

我们如图可知，我们要对四个位置进行改变

新节点的pre，next

d1的next

head的prev 

void ltpushback(LTNode* phead, ltdatatype x)
{assert(phead);LTNode* newnode = ltbuynode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

 其中可以看到在双向链表中，我们使用了一级指针，而在单向链表的类似情况下确使用了二级指针，这是为什么呢？

在单向链表中，如果要在头部插入节点（头插），可能需要使用二级指针，因为头插操作可能会改变链表的头指针。而在双向链表的尾插操作中，我们不需要改变链表的头指针。

因为双向链表的哨兵位不需要改变。

2.5双向链表的打印函数 

//打印链表
void ltprint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

2.6双向链表的头插

和尾插相似，也要对四个位置进行更改。

//头插
void ltpushfrond(LTNode* phead, ltdatatype x)
{assert(phead);LTNode* newnode = ltbuynode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

2.7双向链表的头删 

如图所示，只用对两个位置进行处理，分别是前一个节点的next和后一个节点的prev

然后将删除的节点释放即可

void ltpopfront(LTNode* phead)
{assert(!ltempty(phead));//确保不为空链表LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

在删除前我们还要确保不是空链表（双向链表中的空链表指只有哨兵位） 

导入一个验证函数

2.7.1bool验证空链表

//只有一个节点的情况下，链表为空
bool ltempty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

2.8双向链表的尾删 

 和头删相似，只用对两个位置处理

//尾删
void ltpopback(LTNode* phead)
{assert(!ltempty(phead));//确保不为空链表LTNode* del = phead->prev;/*phead->prev = del->prev;*/del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

2.9双向链表的查找函数

其原理就是从第一个个节点遍历到哨兵位在其中进行查找

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

2.10在指定位置后插入

//在指定位置后插入数据
void ltinsert(LTNode* pos,ltdatatype x)
{LTNode* newnode = ltbuynode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}

2.11删除指定位置的节点 

void lterase(LTNode* pos)//删除指定位置的数据
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

通过上面的插入与删除，我们可以总结出一个规律，即

插入部分我们一般要对四个位置进行处理，而删除只需对两个位置，然后释放要删除的节点 

2.12销毁链表 

void ltdestroy(LTNode* phead)//销毁链表
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;}

在上面我们提到过，要对哨兵位进行操作的时候需要使用二级指针，为何此处还是使用一级指针呢？

其实想要在函数中就要使其销毁，肯定是要使用二级指针的，但是如果我们作为一个开发者，其相似函数在前面都是用一级指针，而这里却突然改变，对于用户来说就增加了记忆需求。所以我们在test函数中单独将head释放就可以了。

3.完整代码的实现

.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//双向链表结构
typedef int ltdatatype;
struct Listnode {ltdatatype  data;struct Listnode* next;struct Listnode* prev;
};
typedef struct Listnode LTNode;
LTNode* ltinit();//双向链表的初始化
void ltpushback(LTNode* plist, ltdatatype x);//尾插
void ltprint(LTNode* phead);//打印链表
void ltpushfrond(LTNode* phead, ltdatatype x);//头插
void ltpopback(LTNode* phead);//尾删
void ltpopfront(LTNode* phead);//头删
LTNode* ltfind(LTNode* phead, ltdatatype x);//查找函数
void ltinsert(LTNode* pos, ltdatatype x);//在指定位置后插入数据
void lterase(LTNode* pos);//删除指定位置的数据
void ltdestroy(LTNode* phead);//销毁链表

.c文件（开发） 

#define _CRT_SECURE_NO_WARNINGS
#include"double_linked_list.h"
//创建新节点
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;
}
//双向链表的初始化
LTNode* ltinit()
{LTNode* phead = ltbuynode(-1);return phead;
}
//尾插
//头结点需要发生改变，传二级
//头节点不需要发生改变，传一级
void ltpushback(LTNode* phead, ltdatatype x)
{assert(phead);LTNode* newnode = ltbuynode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}
//打印链表
void ltprint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
//头插
void ltpushfrond(LTNode* phead, ltdatatype x)
{assert(phead);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(!ltempty(phead));//确保不为空链表LTNode* del = phead->prev;/*phead->prev = del->prev;*/del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//头删
void ltpopfront(LTNode* 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)
{LTNode* newnode = ltbuynode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;}
void lterase(LTNode* pos)//删除指定位置的数据
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
void ltdestroy(LTNode* phead)//销毁链表
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;}

.c文件（测试）
 

#define _CRT_SECURE_NO_WARNINGS
#include"double_linked_list.h"
void test1()
{LTNode* plist = ltinit();ltpushback(plist, 1);ltpushback(plist, 2);ltpushback(plist, 3);ltpushfrond(plist, 4);/*ltpopback(plist);ltpopfront(plist);ltprint(plist);*/LTNode* find = ltfind(plist,4);ltinsert(find, 2);lterase(find);/*ltprint(find);*/ltdestroy(plist);plist = NULL;/*if (find == NULL){printf("没找到\n");}else{printf("找到了\n");}*/
}
int main()
{test1();return 0;
}

今天的分享就到这里了，感谢阅读! 

 

http://www.xdnf.cn/news/427339.html

相关文章：

  • 开发与AI融合的Windsurf编辑器
  • 屏幕与触摸调试
  • Retrofit vs Feign: 介绍、对比及示例
  • 关于 javax.validation.constraints的详细说明
  • Visual Studio 项目 .gitignore 文件指南
  • 如何界定合法收集数据？
  • 【C++】【设计模式】生产者-消费者模型
  • EDR与XDR如何选择适合您的网络安全解决方案
  • 自我奖励语言模型：突破人类反馈瓶颈
  • WebGIS开发面试题：前端篇（六）
  • 【递归、搜索与回溯】专题一：递归（二）
  • electron 基础知识
  • 软考软件评测师——计算机组成与体系结构（分级存储架构）
  • 当三维地理信息遇上气象预警：电网安全如何实现“先知先觉”？
  • 项目中会出现的css样式
  • MQTT协议详解：物联网通信的轻量级解决方案
  • JMeter同步定时器 模拟多用户并发访问场景
  • Qt进阶开发：QTcpSocket的详解
  • Leetcode 3542. Minimum Operations to Convert All Elements to Zero
  • APISQL免费版安装教程（视频）
  • java刷题基础知识
  • 【Folium】使用离线地图
  • 我的MCP相关配置记录
  • Cursor 编辑器 的 高级使用技巧与创意玩法
  • JavaScript异步编程 Async/Await 使用详解：从原理到最佳实践
  • 基于RT-Thread的STM32F4开发第三讲——DAC
  • 基于TI AM6442+FPGA解决方案，支持6网口，4路CAN，8个串口
  • 《ffplay 读线程与解码线程分析：从初始化到 seek 操作，对比视频与音频解码的差异》
  • Vue 3.5 ：新特性全解析与开发实践指南
  • MQTT 协议详解：物联网通信的利器