【数据结构】双向链表的接口实现(附图解和源码)
双向链表的接口实现(附图解和源码)
文章目录
- 双向链表的接口实现(附图解和源码)
- 前言
- 一、定义结构体
- 二、接口实现(附图解+源码)
- 1.初始化双向链表
- 2.开辟新空间
- 3.尾插数据
- 4.尾删数据
- 5.打印双向链表中数据
- 6.头插数据
- 7.头删数据
- 8.查找结点位置
- 9.在pos位置之前插入
- 10.删除pos位置
- 11.销毁双向链表
- 三、源代码展示
- 1.test.c(测试+主函数)
- 2.List.h(接口函数的声明)
- 3.List.c(接口函数的实现)
- 总结
前言
本文主要介绍双向链表中增删查改等接口实现,结尾附总源码!
一、定义结构体

代码如下(示例):
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;
二、接口实现(附图解+源码)

这里一共10个接口,我会我都会一 一为大家讲解(图解+源码)
1.初始化双向链表
初始化出一个哨兵位的头结点(用malloc开辟),next和prev都指向自己。具体如下图!


代码如下(示例):
ListNode* ListInit()
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* phead = p;phead->next = phead;phead->prev = phead;return phead;
}
2.开辟新空间
(1)开辟一个链表类型的动态空间,将地址给newnode;
(2)将值放入 newnode 的 data 数据内;
(3)将 newnode 的 next 和 prev 都置为NULL;
注意:1.将malloc开辟空间存到 newnode 里面时,参数为结构体所占的字节大小!2.对 newnode 进行 NULL 判断!
代码如下(示例):
ListNode* BuyListNode(LTDataType x)
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* newNode = p;newNode->data = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}
3.尾插数据



代码如下(示例):
void ListPushBack(ListNode* phead, LTDataType x)//尾插数据
{ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//第一个链接tail->next = newnode;newnode->prev = tail;//第二个链接phead->prev = newnode;newnode->next = phead;
}
4.尾删数据
这里需要两次进行断言:



代码如下(示例):
void ListPopBack(ListNode* phead)//尾删
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* tailprev = tail->prev;free(tail);//连接tailprev->next = phead;phead->prev = tailprev;
}
5.打印双向链表中数据

代码如下(示例):
void ListPrint(ListNode* phead)//打印数据
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
6.头插数据
头插数据也是很简单的一个接口,链接两次即可,如下图!

代码如下(示例):
void ListPushFront(ListNode* phead, LTDataType x)//头插
{assert(phead);ListNode* newNode = BuyListNode(x);ListNode* next = phead->next;phead->next = newNode;newNode->prev = phead;newNode->next = next;next->prev = newNode;
}
7.头删数据
在头删数据时和尾删数据一样都需要进行两次断言!如下图!




代码如下(示例):
void ListPopFront(ListNode* phead)//头删
{assert(phead);assert(phead->next != phead);ListNode* next = phead->next;ListNode* nextNext = next->next;phead->next = nextNext;nextNext->prev = phead;free(next);
}
8.查找结点位置
这个比较简单,和单链表一样,直接用cur遍历即可,直接上代码:
代码如下(示例):
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
9.在pos位置之前插入


代码如下(示例):
void ListInsert(ListNode* pos, LTDataType x)//pos位置之前插入
{assert(pos);ListNode* newNode = BuyListNode(x);ListNode* posPrev = pos->prev;// posPrev newnode posposPrev->next = newNode;newNode->prev = posPrev;newNode->next = pos;pos->prev = newNode;
}
根据ListInsert接口我们可以把头插和尾插进行改版,如下图!


10.删除pos位置



代码如下(示例):
void ListErase(ListNode* pos)//删除pos位置
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);pos = NULL;prev->next = next;next->prev = prev;
}
11.销毁双向链表


代码如下(示例):
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}
三、源代码展示
1.test.c(测试+主函数)
代码如下(示例):
#include "list.h"
void Testlist1()
{ListNode* n1 = ListInit();ListPushBack(n1, 1);//尾插ListPushBack(n1, 2);//尾插//ListPushBack(n1, 3);//尾插//ListPushBack(n1, 4);//尾插//ListPushBack(n1, 5);//尾插//ListPopFront(n1);//头删//ListPopBack(n1);//尾删//ListPushFront(n1, 0);//头插ListPrint(n1);
}
void Testlist2()
{ListNode* n1 = ListInit();ListPushBack(n1, 1);//尾插ListPushBack(n1, 2);//尾插ListPushBack(n1, 3);//尾插ListPushBack(n1, 4);//尾插ListPushBack(n1, 5);//尾插ListNode* p = ListFind(n1, 5);printf("%d \n", p->data);
}
void Testlist3()
{ListNode* n1 = ListInit();ListPushBack(n1, 1);//尾插ListPushBack(n1, 2);//尾插ListPushBack(n1, 3);//尾插ListPushBack(n1, 4);//尾插ListPushBack(n1, 5);//尾插//ListNode* p = ListFind(n1, 5);//ListInsert(p, 0);ListDestory(n1);ListPrint(n1);
}
int main()
{//Testlist1();//Testlist2();Testlist3();return 0;
}
2.List.h(接口函数的声明)
代码如下(示例):
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <errno.h>
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}ListNode;
ListNode* ListInit();//初始化双向链表
void ListPushBack(ListNode* phead, LTDataType x);//尾插
void ListPopBack(ListNode* phead);//尾删
void ListPushFront(ListNode* phead, LTDataType x);//头插
void ListPopFront(ListNode* phead);//头删
void ListPrint(ListNode* phead);//打印
ListNode* ListFind(ListNode* phead, LTDataType x);//查找数据
void ListInsert(ListNode* pos, LTDataType x);//pos位置之前插入
void ListErase(ListNode* pos);//删除pos位置
void ListDestory(ListNode* phead);//销毁双向链表
3.List.c(接口函数的实现)
代码如下(示例):
#include "list.h"
ListNode* ListInit()
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* phead = p;phead->next = phead;phead->prev = phead;return phead;
}
ListNode* BuyListNode(LTDataType x)
{ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == NULL){perror(errno);}ListNode* newNode = p;newNode->data = x;newNode->next = NULL;newNode->prev = NULL;return newNode;
}
void ListPushBack(ListNode* phead, LTDataType x)//尾插数据
{ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//第一个链接tail->next = newnode;newnode->prev = tail;//第二个链接phead->prev = newnode;newnode->next = phead;//ListInsert(phead, x);
}
void ListPrint(ListNode* phead)//打印数据
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
void ListPopBack(ListNode* phead)//尾删
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* tailprev = tail->prev;free(tail);//连接tailprev->next = phead;phead->prev = tailprev;
}
void ListPushFront(ListNode* phead, LTDataType x)//头插
{assert(phead);ListNode* newNode = BuyListNode(x);ListNode* next = phead->next;phead->next = newNode;newNode->prev = phead;newNode->next = next;next->prev = newNode;//ListInsert(phead->next, x);
}
void ListPopFront(ListNode* phead)//头删
{assert(phead);assert(phead->next != phead);ListNode* next = phead->next;ListNode* nextNext = next->next;phead->next = nextNext;nextNext->prev = phead;free(next);
}
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
void ListInsert(ListNode* pos, LTDataType x)//pos位置之前插入
{assert(pos);ListNode* newNode = BuyListNode(x);ListNode* posPrev = pos->prev;// posPrev newnode posposPrev->next = newNode;newNode->prev = posPrev;newNode->next = pos;pos->prev = newNode;
}
void ListErase(ListNode* pos)//删除pos位置
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);pos = NULL;prev->next = next;next->prev = prev;
}
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}
总结
以上就是今天要讲的内容,本文介绍双向链表的接口实现(附图解和源码)。
如果我的博客对你有所帮助记得三连支持一下,感谢大家的支持!

相关文章:
【数据结构】双向链表的接口实现(附图解和源码)
双向链表的接口实现(附图解和源码) 文章目录双向链表的接口实现(附图解和源码)前言一、定义结构体二、接口实现(附图解源码)1.初始化双向链表2.开辟新空间3.尾插数据4.尾删数据5.打印双向链表中数据6.头插数…...
数据结构与算法之[把数字翻译成字符串]动态规划
前言:最近在刷动态规划的算法题目,感觉这一类题目还是有一点难度的,但是不放弃也还是能学好的,今天给大家分享的是牛客网中的编程题目[把数字翻译成字符串],这是一道经典的面试题目,快手,字节跳…...
java 面向对象三大特性之多态 万字详解(超详细)
目录 前言 : 一、为什么需要多态 : 1.白璧微瑕 : 2.举栗(请甘雨,刻晴,钟离吃饭): 3.代码 : 4.问题 : 二、什么是多态 : 1.定义 : 2.多态的实现步骤(重要) : 三、多态的使用 : 1.多态中成员方法的使用(重要…...
git push origin master 情况
📢📢📢📣📣📣哈喽!大家好,我是「奇点」,江湖人称 singularity。刚工作几年,想和大家一同进步🤝🤝一位上进心十足的【Java ToB端大厂领…...
ElasticSearch查询优化routing
如果一个索引分片多达一百,再加上每个分片数据量大的情况下ES查询速度会慢,这种情况可以根据业务情况考虑使用_routing优化。 _routing 路由 当索引一个文档的时候,文档会被存储在一个主分片上。在存储时一般都会有多个主分片。Elasticsearch 如何知道一个文档应该放置在哪…...
【HashMap 1.7和1.8】
Java中的HashMap是一种常用的数据结构,用于存储键值对。在Java 1.7和1.8中,HashMap的实现有一些不同。 Java 1.7中的HashMap实现是基于“拉链法”的哈希表。每个哈希桶(bucket)是一个链表,存储了散列值相同的键值对。当键值对数量过多时&…...
【Zabbix实战之故障处理篇】Zabbix监控中文乱码问题解决方法
【Zabbix实战之故障处理篇】Zabbix监控中文乱码问题解决方法 一、问题展现1.查看Zabbix仪表盘2.问题分析二、检查Zabbix环境1.检查Zabbix监控主机2.检查Zabbix各组件状态三、在宿主机安装中文字体库1.安装中文字体2.查看字体文件四、安装中文字库1.查看Zabbix所有组件容器2.拷贝…...
学习(mianshi)必备-ClickHouse高性能查询/写入和常见注意事项(五)
目录 一、ClickHouse高性能查询原因-稀疏索引 二、ClickHouse高性能写入-LSM-Tree存储结构 什么是LSM-Tree 三、ClickHouse的常见注意事项和异常问题排查 一、ClickHouse高性能查询原因-稀疏索引 密集索引: 在密集索引中,数据库中的每个键值都有一个索引记录&…...
在Kotlin中探索 Activity Results API 极简的解决方案
Activity Results APIActivity Result API提供了用于注册结果、启动结果以及在系统分派结果后对其进行处理的组件。—Google官方文档https://developer.android.google.cn/training/basics/intents/result?hlzh-cn一句话解释:官方Jetpack组件用于代替startActivity…...
样式冲突太多,记一次前端CSS升级
目前平台前端使用的是原生CSSBEM命名,在多人协作的模式下,容易出现样式冲突。为了减少这一类的问题,提升研效,我调研了业界上主流的7种CSS解决方案,并将最终升级方案落地到了工程中。 样式冲突的原因 目前遇到的样式…...
如何解决报考PMP的那些问题?
关于PMP的报考条件,报考PMP都需要什么条件呢?【学历条件】:需要满足23周岁/高中毕业5年以上/大专以上学历,三个满足一个即可;【PDU条件】:报考PMP需要PDU证明(学习项目管理课程的学时证明&#…...
数据结构栈的经典OJ题【leetcode最小栈问题大剖析】【leetcode有效的括号问题大剖析】
目录 0.前言 1.最小栈 1.1 原题展示 1.2 思路分析 1.2.1 场景引入 1.2.2 思路 1.3 代码实现 1.3.1 最小栈的删除 1.3.2 最小栈的插入 1.3.3 获取栈顶元素 1.3.4 获取当前栈的最小值 2. 有效的括号 0.前言 本篇博客已经把两个关于栈的OJ题分块,可以根据目…...
数据结构与算法之打家劫舍(一)动态规划思想
动态规划里面一部题目打家劫舍是一类经典的算法题目之一,他有各种各样的变式,这一篇文章和大家分享一下打家劫舍最基础的一道题目,掌握这一道题目,为下一道题目打下基础。我们直接进入正题。一.题目大家如果刚接触这样的题目&…...
无人驾驶路径规划论文简要
A Review of Motion Planning Techniques for Automated Vehicles综述和分类0Motion Planning for Autonomous Driving with a Conformal Spatiotemporal Lattice从unstructured环境向structured环境的拓展,同时还从state lattice拓展到了spatiotemporal lattice从而…...
C++ sort()函数和priority_queue容器中比较函数的区别
普通的queue是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。priority_queue中元素被赋予优先级。在创建的时候根据优先级进行了按照从大到小或者从小到大进行了自动排列(大顶堆or小顶堆)。可以以O(log n) 的效率查找…...
STM32开发(14)----CubeMX配置ADC
CubeMX配置ADC前言一、什么是ADC?二、实验过程1.单通道ADC采集STM32CubeMX配置代码实现2.多通道ADC采样(非DMA)STM32CubeMX配置代码实现3.多通道ADC采样(DMA)STM32CubeMX配置代码实现总结前言 本章介绍使用STM32CubeMX对ADC进行配置的方法&a…...
Simple RNN、LSTM、GRU序列模型原理
一。循环神经网络RNN 用于处理序列数据的神经网络就叫循环神经网络。序列数据说直白点就是随时间变化的数据,循环神经网络它能够根据这种数据推出下文结果。RNN是通过嵌含前一时刻的状态信息实行训练的。 RNN神经网络有3个变种,分别为Simple RNN、LSTM、…...
【原创】java+swing+mysql生肖星座查询系统设计与实现
今天我们来开发一个比较有趣的系统,根据生日查询生肖星座,输入生日,系统根据这个日期自动计算出生肖和星座信息反馈到界面。我们还是使用javaswingmysql去实现这样的一个系统。 功能分析: 生肖星座查询系统,顾名思义…...
CentOS 环境 OpneSIPS 3.1 版本安装及使用
文章目录1. OpenSIPS 源码下载2. 工具准备3. 编译安装4. opensips-cli 工具安装5. 启动 OpenSIPS 实例1. OpenSIPS 源码下载 使用以下命令即可下载 OpenSIPS 的源码,笔者下载的是比较稳定的 3.1 版本,读者有兴趣也可前往 官方传送门 sudo git clone htt…...
SQL95 从 Products 表中检索所有的产品名称以及对应的销售总数
描述 Products 表中检索所有的产品名称:prod_name、产品id:prod_idprod_idprod_namea0001egga0002socketsa0013coffeea0003colaOrderItems代表订单商品表,订单产品:prod_id、售出数量:quantityprod_idquantitya0001105…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
