数据结构——lesson4带头双向循环链表实现

2024-02-29 21:04
文章标签 实现 链表 数据结构 双向 循环 带头 lesson4

本文主要是介绍数据结构——lesson4带头双向循环链表实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言✨✨

💥个人主页：大耳朵土土垚-CSDN博客

💥 所属专栏：数据结构学习笔记​​​​​​

💥双链表与单链表的区分：单链表介绍与实现

💥对于malloc函数有疑问的:动态内存函数介绍

   感谢大家的观看与支持🌹🌹🌹 

   有问题可以写在评论区或者私信我哦~

 

目录

前言✨✨

一、💥💥什么是带头双向循环链表？

二、🥳🥳带头双向循环链表的实现 

1 .搭建链表基础

2.从内存中开辟一个节点

3. 创建返回链表的头结点

4.双向链表销毁

5.双向链表打印 

6.双向链表尾插 

7.双向链表尾删

8.双向链表头插 

9.双向链表头删 

10.双向链表查找

11.双向链表在pos的前面进行插入 

12.双向链表删除pos位置的节点 

三、💫💫拓展

四、🎉🎉结言 

一、💥💥什么是带头双向循环链表？

 

带头双向循环链表（Doubly Circular Linked List with a Head）是一种链表数据结构，它具有以下特点：

1.头节点：带头双向循环链表包含一个头节点，它位于链表的起始位置，并且不存储实际数据。头节点的前驱指针指向尾节点，头节点的后继指针指向第一个实际数据节点。

2.循环连接：尾节点的后继指针指向头节点，而头节点的前驱指针指向尾节点，将链表形成一个循环连接的闭环。这样可以使链表在遍历时可以无限循环，方便实现循环操作。

3.双向连接：每个节点都有一个前驱指针和一个后继指针，使得节点可以向前和向后遍历。前驱指针指向前一个节点，后继指针指向后一个节点。

        总结:带头双向循环链表可以支持在链表的任意位置进行插入和删除操作，并且可以实现正向和反向的循环遍历。通过循环连接的特性，链表可以在连续的循环中遍历所有节点，使得链表的操作更加灵活和高效。

如下图所示：

 

 

结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。 

二、🥳🥳带头双向循环链表的实现 

1 .搭建链表基础

带头双向循环链表需要三个变量，两个存放指向前后节点的指针，另一个存放数据

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//存放数据struct ListNode* next;//指向下一个节点struct ListNode* prev;//指向上一个节点
}ListNode;

2.从内存中开辟一个节点

使用malloc函数开辟节点

//从内存中开辟一个节点
ListNode* BuyNode(LTDataType x)
{ListNode* buynode = (ListNode*)malloc(sizeof(struct ListNode));if (buynode == NULL)//开辟失败{perror("malloc fail");}buynode->data = x;buynode->next = NULL;buynode->prev = NULL;}

 

3. 创建返回链表的头结点
 

开始时头节点两个指针都指向自己

//创建返回链表的头结点.
ListNode* ListCreate()
{ListNode* head = BuyNode(-1);//这里将头节点数据设为-1，任意数都可以head->next = head;head->prev = head;return head;
}

 

4.双向链表销毁

 malloc开辟空间后要使用free销毁内存空间，防止内存泄漏

// 双向链表销毁
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;//头节点最后销毁while (cur != pHead)//循环一遍{ListNode* next = cur->next;//保存下一个节点，防止丢失free(cur);//销毁节点cur = next;}free(pHead);//销毁头节点
}

5.双向链表打印 

 

//双向链表打印
void ListPrint(ListNode* pHead)
{assert(pHead);if (pHead->next == pHead)//没有节点的情况，也可以不考虑{printf("pHead<=>pHead");return;}//有节点的情况printf("pHead<=>");//先打印pHeadListNode* cur = pHead->next;while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("pHead");//因为最后也是指向pHead
}

 

没有节点情况打印如下： 

6.双向链表尾插 

 

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//找尾节点,保存原来的尾//尾节点就是pHead->prevListNode* tail = pHead->prev;//开辟新节点ListNode* newnode = BuyNode(x);//尾插pHead->prev = newnode;newnode->next = pHead;newnode->prev = tail;tail->next = newnode;}

 

结果如下：

 

7.双向链表尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//没有节点不能尾删，头节点pHead不算if (pHead->next == pHead){printf("没有添加节点\n");return;}//找尾节点，以及尾节点的前一个节点ListNode* tail = pHead->prev;ListNode* tailprev = tail->prev;//尾删tailprev->next = pHead;pHead->prev = tailprev;free(tail);//释放内存空间
}

 结果如下：

8.双向链表头插 

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//找头以外的第一个节点ListNode* headnext = pHead->next;//创建新节点ListNode* newnode = BuyNode(x);//头插pHead->next = newnode;newnode->next = headnext;newnode->prev = pHead;headnext->prev = newnode;
}

 

结果如下：

9.双向链表头删 

 

// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);//判断有没有节点，头节点pHead除外if (pHead->next == pHead){printf("没有添加节点\n");return;}//有节点//找头节点以及头节点的下一个节点ListNode* head = pHead->next;ListNode* headnext = head->next;//头删pHead->next = headnext;headnext->prev = pHead;free(head);//释放内存空间
}

 

 结果如下：

 

10.双向链表查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);//判断有无节点if (pHead->next == pHead){printf("没有添加节点\n");return;}ListNode* cur = pHead->next;//遍历查找while (cur){if (cur->data == x){return cur;//找到返回地址}cur = cur->next;}
}

结果如下：

11.双向链表在pos的前面进行插入 

在pos位置前面插入原理和头插尾插相似

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);//找到pos前一个节点ListNode* posprev = pos->prev;//创建新节点ListNode* newnode = BuyNode(x);//在pos前插入posprev->next = newnode;newnode->next = pos;newnode->prev = posprev;pos->prev = newnode;}

结果如下：

 

12.双向链表删除pos位置的节点 

在pos位置删除原理和头删尾删相似

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);//找到pos前一个节点ListNode* posprev = pos->prev;//找打pos后一个节点ListNode* posnext = pos->next;//删除pos位置节点posprev->next = posnext;posnext->prev = posprev;free(pos);//释放内存空间}

结果如下：

三、💫💫拓展

思考：在pos之前插入与头插尾插是否有关？

           在pos位置删除与头删尾删是否相似？

 

我们发现pos位置前插入函数代码似乎可以复用在头插尾插；

pos位置删除函数代码似乎可以复用在头删尾删；

下面我们一起来实现

1.尾插头插 

//尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);//找尾节点,保存原来的尾//尾节点就是pHead->prev//ListNode* tail = pHead->prev;开辟新节点//ListNode* newnode = BuyNode(x);尾插//pHead->prev = newnode;//newnode->next = pHead;//newnode->prev = tail;//tail->next = newnode;ListInsert(pHead, x);}//头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);//找头以外的第一个节点//ListNode* headnext = pHead->next;创建新节点//ListNode* newnode = BuyNode(x);头插//pHead->next = newnode;//newnode->next = headnext;//newnode->prev = pHead;//headnext->prev = newnode;ListInsert(pHead->next, x);}

2.尾删，头删

 

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//没有节点不能尾删，头节点pHead不算if (pHead->next == pHead){printf("没有添加节点\n");return;}找尾节点，以及尾节点的前一个节点//ListNode* tail = pHead->prev;//ListNode* tailprev = tail->prev;尾删//tailprev->next = pHead;//pHead->prev = tailprev;//free(tail);//释放内存空间ListErase(pHead->prev);
}// 双向链表头删
void ListPopFront(ListNode* pHead)
{assert(pHead);//判断有没有节点，头节点pHead除外if (pHead->next == pHead){printf("没有添加节点\n");return;}有节点找头节点以及头节点的下一个节点//ListNode* head = pHead->next;//ListNode* headnext = head->next;头删//pHead->next = headnext;//headnext->prev = pHead;//free(head);//释放内存空间ListErase(pHead->next);
}

 

 运行结果依然不受影响：

 

四、🎉🎉结言 

        我们通过上面的学习发现，相似的代码的重复利用可以大大减少我们写代码的时间与精力，提高我们工作学习的效率；双向链表尽管结构较单链表复杂，但其实现却比单链表简单得多，相信大家对此都深有体会，此外数据结构的题目我们可以通过画图来很好的获得思路与接替步骤，以上就是带头双向循环链表的相关知识啦~完结撒花~🎉🎉🌹🌹🌹

这篇关于数据结构——lesson4带头双向循环链表实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/760078。

相关文章

Python使用Tenacity一行代码实现自动重试详解

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门：一行代码实现优雅重试精细控制：让重试按我
阅读更多...
Redis客户端连接机制的实现方案

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连
阅读更多...
Python实现网格交易策略的过程

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略，其核心思想是在价格上下预设多个“网格”，当价格触发特定网格时执行买
阅读更多...
python设置环境变量路径实现过程

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法：临时设置（Windows用`set`,Linux/macOS用`export`）、永久设置（系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量（适用于当前会话）永久设置环境变量（Windows系统
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...
Spring Security 单点登录与自动登录机制的实现原理

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录（SSO）与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录（SSO）1.2 自动登录（Remember Me）二、代码分析三、
阅读更多...
PyCharm中配置PyQt的实现步骤

PyCharm中配置PyQt的实现步骤

《PyCharm中配置PyQt的实现步骤》PyCharm是JetBrains推出的一款强大的PythonIDE,结合PyQt可以进行pythion高效开发桌面GUI应用程序,本文就来介绍一下PyCha... 目录1. 安装China编程PyQt1.PyQt 核心组件2. 基础 PyQt 应用程序结构3. 使用 Q
阅读更多...
Python实现批量提取BLF文件时间戳

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF（BinaryLoggingFormat）作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析：从文件遍历到数据导出1. 环境准备与依赖库
阅读更多...
linux下shell脚本启动jar包实现过程

linux下shell脚本启动jar包实现过程

《linux下shell脚本启动jar包实现过程》确保APP_NAME和LOG_FILE位于目录内,首次启动前需手动创建log文件夹,否则报错,此为个人经验,供参考,欢迎支持脚本之家... 目录linux下shell脚本启动jar包样例1样例2总结linux下shell脚本启动jar包样例1#!/bin
阅读更多...
go动态限制并发数量的实现示例

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发，所以面试百分百会问到
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2