数据结构之双向链表

目录

双向链表的基本概念和结构

初始化

尾插

头插

尾删

头删

查找

在指定位置之后插入

删除指定位置节点

判空

销毁 

完整代码

测试代码

双向链表的基本概念和结构

双向链表（Doubly Linked List）‌是一种链式存储结构，每个节点除了存储数据外，还包含两个指针，分别指向前一个节点（prev）和后一个节点（next）。这种结构使得双向链表可以从头到尾遍历，也可以从尾到头遍历，非常灵活‌。

双向链表的每个节点包含以下部分：

  • ‌数据元素‌：可以是任何类型的数据，如整数、浮点数、字符串或对象。
  • ‌prev指针‌：指向前一个节点的指针。
  • ‌next指针‌：指向下一个节点的指针。

双向链表通常包含一个头节点（哨兵位节点），这个节点不存储有效数据，只有指向第一个有效节点的next指针和指向尾节点的prev指针。只要链表存在，哨兵位节点就存在‌。

‌优点‌：

  • ‌双向遍历‌：可以从两个方向遍历链表，既可以从头到尾，也可以从尾到头。
  • ‌插入和删除操作高效‌：在已知前后节点的情况下，插入或删除操作可以直接进行，不需要遍历整个链表。
  • ‌动态内存分配‌：链表可以在运行时动态地分配和释放内存，适合需要频繁增删操作的场景。

初始化

LTNode* ByNode(LTDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("申请失败!\n");exit(1);}//自成循环newnode->val = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}void LTInit(LTNode **phead)
{//创建一个哨兵卫节点//*phead指向哨兵卫*phead = ByNode(-1);
}

初始化的目的就是创建一个哨兵卫节点，传参为二级指针是因为初始化时要对哨兵卫进行改变，改变一个指针就要传这个指针的地址，传指针的地址就要用二级指针来接收。

让每一个新增节点都先自成循环，这样方便与链表连接起来。

尾插

void LTPushBack(LTNode* phead, LTDatatype x)
{//不对哨兵卫进行改变，所以传一级指针assert(phead); //哨兵卫不能为空LTNode* newnode = ByNode(x);newnode->prev = phead->next;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

 

 与尾插相关的只有哨兵卫的prev指针指向的数据和哨兵卫。哨兵卫的prev指针指向的是链表中的最后一个数据，不管该数据是否是哨兵卫都没有关系。先让newnode的prev指针指向最后一个数据，next指针指向哨兵卫，再让最后一个数据的next指针指向newnode。

头插

void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = ByNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

 头插是往第一个有效数据前面插入，而不是在哨兵卫前面插入。先让newnode的next指针指向最后一个数据，newnode的prev指针指向哨兵卫，再让第一个有效数据的prev指针指向newnode，哨兵卫的next指针指向newnode就完成了头插。

尾删

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

 

尾删的前提是你要有有效的数据，那么哨兵卫节点的next指针就不能指向哨兵卫自己。首先要记录最后的一个数据存储在del变量里，先让del的前一个数据的next指针指向哨兵卫，哨兵卫的prev指针指向del的前一个数据。然后释放del空间，将del置为空。

头删

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

 首先要记录第一个有效数据存储在del变量里，先让del的下一个数据的prev指针指向哨兵卫，哨兵卫的next指针指向del的下一个数据。然后释放del空间，将del置为空。

查找

LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->val == x)return pcur;pcur = pcur->next;}return NULL;
}

 直接从链表的第一个有效数据开始遍历，结束条件是遍历到哨兵卫就结束，如果节点的值是你要查询的值，就返回这个节点。如果链表中没有你要查找的数据，就返回空。

在指定位置之后插入

void LTInsertBack(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = ByNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

这个接口的原理是根据查找函数返回的节点进行插入。如果你指定在d2的后面插入数据，你就要先查找d2在哪里，返回这个节点。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;
}

 这个接口的原理是根据查找函数返回的节点进行删除。让pos节点的next指向的节点和prev指向的节点连接起来，然后释放pos节点，将pos节点置为空。

判空

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

判断该链表是否有有效数据，直接查看哨兵卫指向第一个有效节点的next指针是否指向哨兵卫，如果是，则说明该链表中只有一个哨兵卫，没有有效数据，就说该链表为空链表。

销毁 

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

 链表的销毁要先从第一个有效数据开始删，最后释放掉哨兵卫节点。先定义一个指针pcur指向哨兵卫节点的next指针指向的节点，然后开始遍历链表进行删除。

完整代码

#define _CRT_SECURE_NO_WARNINGS#include "list.h"//申请节点
LTNode* ByNode(LTDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("申请失败!\n");exit(1);}//自成循环newnode->val = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}void LTInit(LTNode **phead)
{//创建一个哨兵卫节点//*phead指向哨兵卫*phead = ByNode(-1);
}void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->val);pcur = pcur->next;}printf("\n");
}//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{//不对哨兵卫进行改变，所以传一级指针assert(phead); //哨兵卫不能为空LTNode* newnode = ByNode(x);newnode->prev = phead->next;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = ByNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != 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->val == x)return pcur;pcur = pcur->next;}return NULL;
}//在指定位置之后插入
void LTInsertBack(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = ByNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}//在指定位置之前插入
void LTInitFront(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = ByNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}//删除pos节点
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

测试代码

#define _CRT_SECURE_NO_WARNINGS#include "list.h"void test()
{LTNode *plist = NULL;LTInit(&plist);  //创建了一个哨兵卫头插//LTPushBack(plist, 1);//LTPrint(plist);//LTPushBack(plist, 2);//LTPrint(plist);//LTPushBack(plist, 3);//LTPrint(plist);//尾插LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);尾删//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);头删//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//查找LTNode* find = LTFind(plist, 2);//if (find)//	printf("找到了\n");//else//	printf("没有找到\n");//在指定位置之后插入//LTInsertBack(find, 66);//LTPrint(plist);//LTInsertBack(find, 88);//LTPrint(plist);在指定位置之前插入//LTInitFront(find, 66);//LTPrint(plist);//LTInitFront(find, 88);//LTPrint(plist);删除pos节点//LTErase(find);//LTPrint(plist);//判空//if (LTEmpty(plist))//	printf("为空\n");//else//	printf("不为空\n");LTDestory(plist);
}int main()
{test();return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/170.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

[程序设计]—代理模式

[程序设计]—代理模式

[程序设计]—代理模式👳 本文章记录学习于——52.面向切面：AOP-场景模拟_哔哩哔哩_bilibili 最近闲来无事，在学习Spring的源码： 后面慢慢更新源码系列blog，希望多多关注🙏🙏 目前已经总结的b…
阅读更多...
网易云音乐登录两部手机：IP属地归属何方？

网易云音乐登录两部手机：IP属地归属何方？

在数字化生活日益普及的今天，音乐平台成为了我们日常娱乐不可或缺的一部分。网易云音乐，作为众多音乐爱好者的首选，其丰富的音乐资源和个性化的推荐算法深受用户喜爱。然而，随着多设备登录成为常态，一个问题也随之浮现…
阅读更多...
spark汇总

spark汇总

目录 描述运行模式1. Windows模式代码示例 2. Local模式3. Standalone模式 RDD描述特性RDD创建代码示例（并行化创建）代码示例（读取外部数据）代码示例（读取目录下的所有文件） 算子DAGSparkSQLSparkStreaming…
阅读更多...
SQL多表联查、自定义函数（字符串分割split）、xml格式输出

SQL多表联查、自定义函数（字符串分割split）、xml格式输出

记录一个报表的统计，大概内容如下： 多表联查涉及的报表有：房间表、买家表、合同表、交易表、费用表、修改记录表 注意：本项目数据库使用的是sqlserver（mssql），非mysql。 难点1:业主信息&#…
阅读更多...
实用操作系统学习笔记

实用操作系统学习笔记

第1章 操作系统概述 操作系统基本概念 【基础知识】 操作系统：控制和管理整个计算机系统的硬件和软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。操作系统是计算机系统中最基本的…
阅读更多...
硬件设计-齐纳管

硬件设计-齐纳管

目录 摘要 详情 齐纳管的工作电流、 摘要 齐纳管（Zener Diode）是一种特殊的二极管，它能够在特定的反向电压下保持电流稳定。正常情况下，二极管只允许正向电流通过，而阻止反向电流流过。而齐纳管在一定的反向电压下可…
阅读更多...
linux网络 | https前置知识 | 数据加密与解密、数据摘要

linux网络 | https前置知识 | 数据加密与解密、数据摘要

前言:本节内容讲述https的相关内容。 https博主会着重讲解https如何让一个请求和一个响应能够安全的进行交互。 https博主将用两篇文章进行讲解。本篇是两篇中第一篇。会把http的安全问题引出来， 然后说一下https的基本解决方法。 下面废话不多说， 开始我…
阅读更多...
小目标检测难点分析和解决策略

小目标检测难点分析和解决策略

目录 一、背景 二、检测难点 三、主流改进方法 3.1 基于改进数据增强的小目标检测算法 3.1.1 监督数据增强方法 3.1.2 无监督数据增强方法 3.2. 基于改进特征提取的小目标检测算法 3.2.1. 扩张卷积 3.2.2. 特征增强 3.2.3. 多尺度特征提取 3.2.4. 注意力机制 3.3 基…
阅读更多...
Java 继承

Java 继承

目录 1. 继承概述 2. 继承好处 3. 继承格式 4. 继承规定 5. debug 调试 6. 方法重写 6.1 概述 6.2 规定 7. super 关键字 7.1 概述 7.2 使用 7.3 在构造器中使用 8. 子类对象实例化的全过程 9. 练习 1. 继承概述 举例：Person 类中有name&#xff0c…
阅读更多...
CES Asia 2025科技盛宴，AI智能体成焦点

CES Asia 2025科技盛宴，AI智能体成焦点

2025第七届亚洲消费电子技术展（CES Asia赛逸展）将在北京拉开帷幕，AI智能体有望成为展会的核心亮点。 深圳市人工智能行业协会发文表示全力支持CES Asia 2025（赛逸展），称其为人工智能领域的创新发展提供了强…
阅读更多...
HTMLHTML5革命：构建现代网页的终极指南 - 0. 课程目录设计

HTMLHTML5革命：构建现代网页的终极指南 - 0. 课程目录设计

结构清晰，层层递进 课程从基础知识（如HTML学前必知）开始，逐步深入到高级应用（如PWA配置和WebApp优化）。每个模块都有明确的目标，适合零基础学员逐步掌握HTML。 覆盖范围广 这套课程涵盖了HTM…
阅读更多...
大型语言模型（LLM）中的tokens是什么

大型语言模型（LLM）中的tokens是什么

大型语言模型（LLM）中的tokens是什么 在大型语言模型（LLM）中，tokens是文本处理的基本单位，它可以是一个单词、一个字符、一个标点符号，或者是一个特殊的标记。以下是关于tokens的详细介绍及举例： 一、tokens的定义和作用 定义：tokens是将文本分割成的一个个有意义的…
阅读更多...
嵌入式C语言：二维数组

嵌入式C语言：二维数组

目录 一、二维数组的定义 二、内存布局 2.1. 内存布局特点 2.2. 内存布局示例 2.2.1. 数组元素地址 2.2.2. 内存布局图（简化表示） 2.3. 初始化对内存布局的影响 三、访问二维数组元素 3.1. 常规下标访问方式 3.2. 通过指针访问 3.2.1. 指向数…
阅读更多...
Java进阶-在Ubuntu上部署SpringBoot应用

Java进阶-在Ubuntu上部署SpringBoot应用

随着云计算和容器化技术的普及，Linux 服务器已成为部署 Web 应用程序的主流平台之一。Java 作为一种跨平台的编程语言，具有广泛的应用场景。本文将详细介绍如何在 Ubuntu 服务器上部署 Java 应用，包括环境准备、应用发布、配置反向代理&#…
阅读更多...
node-sass@4.14.1报错的最终解决方案分享

node-sass@4.14.1报错的最终解决方案分享

输入npm i全安装文件所需的依赖的时候，博主是使用sass去书写的，使用的是node-sass4.14.1和sass-loader7.3.1的版本的，安装的时候老是出现错误， node-sass4.14.1版本不再被支持的原因 node-sass 是一个基于 LibSass 的 Node.js 绑…
阅读更多...
Java设计模式 —— 【行为型模式】命令模式（Command Pattern） 详解

Java设计模式 —— 【行为型模式】命令模式（Command Pattern） 详解

文章目录 模式介绍优缺点适用场景结构案例实现注意事项 模式介绍 有时候需要向某些对象发送请求，但是并不知道请求的接收者是谁，也不知道被请求的操作是什么。此时希望用一种松耦合的方式来设计程序，使得请求发送者和请求接收者能够消除彼此…
阅读更多...
Vue3初学之组件通信

Vue3初学之组件通信

一起进行学习： 在 Vue 3 中，组件通信是一个非常重要的概念，它决定了如何在父子组件之间、兄弟组件之间以及跨层级组件之间传递数据和事件。以下是 Vue 3 中常见的组件通信方式： 父子组件通信 1.1 父组件向子组件传递数据&#x…
阅读更多...
springBoot整合ELK Windowsb版本 (elasticsearch+logstash+kibana)

springBoot整合ELK Windowsb版本 (elasticsearch+logstash+kibana)

springBoot整合ELK Windowsb版本 【elasticsearchlogstashkibana】 下载软件启动服务1、elasticsearch2、kibana3、logstash 集成springboot1、添加依赖2、在logback.xml添加相关配置3、修改logstash 配置4、重启logstash 最后测试 下载软件 elasticsearch 官网 https://www.…
阅读更多...
选择器css

选择器css

1.a标签选择 // 选中所具有herf 的元素 [herf] {color: skyblue; } // 选中所具有herfhttps://fanyi.youdao.com/ 的元素 [herf$"youdao.com"] {color:pink; } // 按此顺序书写 link visited hover active // 未访问状态 a:link {color:orange } // 访问状态 a…
阅读更多...
数据结构大作业——家谱管理系统（超详细！完整代码！）

数据结构大作业——家谱管理系统（超详细！完整代码！）

目录 设计思路： 一、项目背景 二、功能分析 查询功能流程图： 管理功能流程图： 三、设计 四、实现 代码实现： 头文件 结构体 函数声明及定义 创建家谱树头结点 绘制家谱树（打印） 建立右兄弟…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023