数据结构:带头双向循环链表

2024-05-25 14:04

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

目录

前言

链表实现

1.定义节点

2.接口实现

1.开辟新节点

2.初始化

3.打印链表

4.添加节点

头插

尾插

在pos位置之前增加节点

5.删除节点

判空

头删

尾删

删除pos位置的节点

6.查找

7.释放


前言

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

链表实现

1.定义节点

双向循环链表每个节点有两个指针,一个指向前一个,一个指向下一个。

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;

2.接口实现

1.开辟新节点

添加数据的接口都需要开辟新节点,写一个Buynewnode方便复用。

LTNode* Buynewnode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;}

2.初始化

初始化定义哨兵位头结点。

LTNode* LTInit()
{LTNode* phead = Buynewnode(-1);phead->next = phead;phead->prev = phead;return phead;
}

3.打印链表

void LTPrint(LTNode* phead)
{LTNode* cur = phead->next;printf("guard<==>");while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

4.添加节点

头插
LTNode* LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = Buynewnode(x);LTNode* first = phead->next;first->prev = newnode;newnode->next = first;phead->next = newnode;newnode->prev = phead;}
尾插
LTNode* LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = Buynewnode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}
在pos位置之前增加节点
//在pos位置之前插入
LTNode* LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev = pos->prev;LTNode* newnode = Buynewnode(x);newnode->next = pos;pos->prev = newnode;newnode->prev = prev;prev->next = newnode;
}

头插和尾插可以复用这段代码。 

5.删除节点

判空

当链表只剩下头结点就不能再删除,所以要判空。

bool JudgeEmpty(LTNode* phead)
{return phead->next == phead;
}
头删
LTNode* LTPopFront(LTNode* phead)
{assert(phead);assert(!JudgeEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);
}
尾删
LTNode* LTPopBack(LTNode* phead)
{assert(phead);assert(!JudgeEmpty(phead));LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);
}
删除pos位置的节点
//删除pos位置的节点
LTNode* LTErase(LTNode* pos)
{assert(pos);LTNode* posnext = pos->next;LTNode* posprev = pos->prev;posnext->prev = posprev;posprev->next = posnext;free(pos);
}

6.查找

LTNode* LTFind(LTDataType x,LTNode* phead)
{LTNode* cur = phead->next;while(cur != phead){cur = cur->next;if (cur->data == x){return cur;}}return NULL;
}

7.释放


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

上面的代码有很多指针不太好想,借助画图会方便许多!!! 

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



http://www.chinasem.cn/article/1001712

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出(OutOfMemoryError),所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本(可能导致内存溢出)2.2 修改后的版本问题在

JAVA中while循环的使用与注意事项

《JAVA中while循环的使用与注意事项》:本文主要介绍while循环在编程中的应用,包括其基本结构、语句示例、适用场景以及注意事项,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录while循环1. 什么是while循环2. while循环的语句3.while循环的适用场景以及优势4. 注意