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

2024-09-01 15:04

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

目录

一、前言:

单链表存在缺陷:不能找到前驱,即不能从后往前找数据。

解决方法:双向链表。

二、带头双向循环链表:

1.实现的接口总数

2.建立链表及上述接口

(1)链表的建立

(2)创立新节点的函数

(3)初始化函数

 (4)销毁函数

(5)打印函数

(6)尾插函数

(7).头插函数

(8).头删函数

(9)尾删函数

(10)查找函数

(11)pos位置之前插入x的函数

(12)删除pos位置的值的函数

三、总结:

1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

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


一、前言:

单链表存在缺陷:不能找到前驱,即不能从后往前找数据。

解决方法:双向链表。


二、带头双向循环链表:

1.实现的接口总数

//初始化函数
ListNode* ListInit();
//摧毁函数
void ListDestory(ListNode* phead);
//打印函数
void ListPrint(ListNode* phead);
//尾插函数
void ListPushBack(ListNode* phead, LTDataType x);
//头插函数
void ListPushFront(ListNode* phead, LTDataType x);
//头删函数
void ListPopFront(ListNode* phead);
//尾删函数
void ListPopBack(ListNode* phead);
//查找函数
ListNode* ListFind(ListNode* phead, LTDataType x);
// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x);
// 删除pos位置的值
void ListErase(ListNode* pos);

2.建立链表及上述接口

(1)链表的建立

typedef int LTDataType;
// 带头双向循环 -- 最有链表结构,任意位置插入删除数据都是O(1)
//除了查找的空间复杂度是O(N)
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}ListNode;

(2)创立新节点的函数

//创建新节点的函数
ListNode* BuyListNode(LTDataType x)
{ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

(3)初始化函数

//初始化函数
ListNode* ListInit()
{ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;
}

 (4)销毁函数

//摧毁函数
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;
}

(5)打印函数

//打印函数,和单链表不一样的是条件不是空指针停止
//而是一个循环从phead->next到phead之间都遍历才停止
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

(6)尾插函数

//尾插函数
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

(7)头插函数

//头插函数
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);first->prev = newnode;newnode->next = first;phead->next = newnode;newnode->prev = phead;
}

(8)头删函数

//头删函数
void ListPopFront(ListNode* phead)
{assert(phead);//assert(phead->next!=phead);//防止头结点被删//ListNode* first = phead->next;//ListNode* second= first->next;删除first后连接建立双向链表//phead->next = second;//second->prev = phead;//free(first);//first = NULL;ListErase(phead->next);
}

(9)尾删函数

//尾删函数
void ListPopBack(ListNode* phead)
{assert(phead);/*assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;*/ListErase(phead->prev);
}

(10)查找函数

//查找函数
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;}

(11)pos位置之前插入x的函数

// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* prev = pos->prev;ListNode* newnode = BuyListNode(x);// prev newnode posprev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}

(12)删除pos位置的值的函数

// 删除pos位置的值
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}

三、总结:

1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

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

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



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

相关文章

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. 注意

Python中的异步:async 和 await以及操作中的事件循环、回调和异常

《Python中的异步:async和await以及操作中的事件循环、回调和异常》在现代编程中,异步操作在处理I/O密集型任务时,可以显著提高程序的性能和响应速度,Python提供了asyn... 目录引言什么是异步操作?python 中的异步编程基础async 和 await 关键字asyncio 模块理论