数据结构——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。

相关文章

C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
C++中悬垂引用(Dangling Reference) 的实现

C++中悬垂引用(Dangling Reference) 的实现

《C++中悬垂引用(DanglingReference)的实现》C++中的悬垂引用指引用绑定的对象被销毁后引用仍存在的情况,会导致访问无效内存,下面就来详细的介绍一下产生的原因以及如何避免,感兴趣... 目录悬垂引用的产生原因1. 引用绑定到局部变量，变量超出作用域后销毁2. 引用绑定到动态分配的对象，对象
阅读更多...
SpringBoot基于注解实现数据库字段回填的完整方案

SpringBoot基于注解实现数据库字段回填的完整方案

《SpringBoot基于注解实现数据库字段回填的完整方案》这篇文章主要为大家详细介绍了SpringBoot如何基于注解实现数据库字段回填的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解... 目录数据库表pom.XMLRelationFieldRelationFieldMapping基础的一些代
阅读更多...
Java HashMap的底层实现原理深度解析

Java HashMap的底层实现原理深度解析

《JavaHashMap的底层实现原理深度解析》HashMap基于数组+链表+红黑树结构,通过哈希算法和扩容机制优化性能,负载因子与树化阈值平衡效率,是Java开发必备的高效数据结构,本文给大家介绍... 目录一、概述：HashMap的宏观结构二、核心数据结构解析1. 数组（桶数组）2. 链表节点（Node
阅读更多...
Java AOP面向切面编程的概念和实现方式

Java AOP面向切面编程的概念和实现方式

《JavaAOP面向切面编程的概念和实现方式》AOP是面向切面编程,通过动态代理将横切关注点（如日志、事务）与核心业务逻辑分离,提升代码复用性和可维护性,本文给大家介绍JavaAOP面向切面编程的概... 目录一、AOP 是什么？二、AOP 的核心概念与实现方式核心概念实现方式三、Spring AOP 的关
阅读更多...
Python实现字典转字符串的五种方法

Python实现字典转字符串的五种方法

《Python实现字典转字符串的五种方法》本文介绍了在Python中如何将字典数据结构转换为字符串格式的多种方法,首先可以通过内置的str()函数进行简单转换;其次利用ison.dumps()函数能够... 目录1、使用json模块的dumps方法：2、使用str方法：3、使用循环和字符串拼接：4、使用字符
阅读更多...
Linux下利用select实现串口数据读取过程

Linux下利用select实现串口数据读取过程

《Linux下利用select实现串口数据读取过程》文章介绍Linux中使用select、poll或epoll实现串口数据读取,通过I/O多路复用机制在数据到达时触发读取,避免持续轮询,示例代码展示设... 目录示例代码（使用select实现）代码解释总结在 linux 系统里，我们可以借助 select、
阅读更多...
Linux挂载linux/Windows共享目录实现方式

Linux挂载linux/Windows共享目录实现方式

《Linux挂载linux/Windows共享目录实现方式》：本文主要介绍Linux挂载linux/Windows共享目录实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录文件共享协议linux环境作为服务端（NFS）在服务器端安装 NFS创建要共享的目录修改 NFS 配
阅读更多...
通过React实现页面的无限滚动效果

通过React实现页面的无限滚动效果

《通过React实现页面的无限滚动效果》今天我们来聊聊无限滚动这个现代Web开发中不可或缺的技术,无论你是刷微博、逛知乎还是看脚本,无限滚动都已经渗透到我们日常的浏览体验中,那么,如何优雅地实现它呢？... 目录1. 早期的解决方案2. 交叉观察者：IntersectionObserver2.1 Inter
阅读更多...
Spring Gateway动态路由实现方案

Spring Gateway动态路由实现方案

《SpringGateway动态路由实现方案》本文主要介绍了SpringGateway动态路由实现方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录前沿何为路由RouteDefinitionRouteLocator工作流程动态路由实现尾巴前沿S
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2