手搓双向循环链表

文章目录

• 前言
• 一、链表的结构
• 二、双向链表
• • 2.1 概念与结构
  • 2.2 实现双向链表
• 总结

前言

上一篇我们学习了单链表的概念以及单链表的实现，但链表可不止单链表一种，今天我们来整体学习链表这个小小卡拉米，Follw me

一、链表的结构

链表的结构多种多样，有带头的不带头的，有单向的，有双向的，还有循环和不循环的
上篇我们只学习了单向不带头不循环链表，但也是挺重要的一种。
请看图

组合起来就有8种之多

上图呈现了各种结构的具象化，虽然有这么多的链表结构，但是我们实际中最常用的还是两种结构：单链表和双向带头循环链表

1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。

二、双向链表

2.1 概念与结构

注意：这⾥的“带头”就是上篇在学习二级指针问题时提到的。
带头链表⾥的头结点，实际为“哨兵位”（我喜欢称它为“烧饼位"），哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的。
当链表有了头结点之后，就可以每次传头指针的地址（一级指针），因为头结点只是放哨，不会改变，所以不管链表其他节点如何改变都不会影响头结点，这里传一级指针，函数传形参也没有关系，不用像实现单链表一样传二级指针，防止首结点改变时改变的是形参。

2.2 实现双向链表

双向循环链表在单链表的基础上 更加方便 基本都是 o（1） 的时间复杂度
更加有效的实现增删改查的功能
让我来手敲实现小小双向循环链表

首先定义一个结点结构体

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;   //  结点储存的值
	ListNode* prev;   //  当前结点的上一个结点地址
	ListNode* next;   //  当前节点的下一个结点地址
}LTNode;

以下函数我将一一斩于马下

LTNode* LTIint()   //  初始化  创建烧饼位  

void LTPrint(LTNode* phead);   // 打印链表  

void LTPushBack(LTNode* phead, LTDataType x);  // 尾部插入

void LTPushFront(LTNode* phead, LTDataType x);  //  头部插入

bool LTEmpty(LTNode* phead);   //  判断链表是否为空

void LTPopBack(LTNode* phead);  //  尾删

void LTPopFront(LTNode* phead);  // 头删

void LTInsert(LTNode* pos, LTDataType x);  //  在pos结点之后插入

void LTErase(LTNode* pos);   //  删除pos结点

LTNode* LTFind(LTNode* phead, LTDataType x);  // 查找结点

void LTDestory(LTNode* phead);   //  销毁链表

首先是链表的初始化，这里的初始化和单链表不同，因为我们引入了“烧饼位”，所以在初始化的时候，创建一个结点就行，然后让它产生自循环，因为此时链表没有任何结点。

LTNode* LTIint()   //  初始化  创建   烧饼位 
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));   //  申请结点空间
	phead->val = -1;   //  因为是烧饼位，储存数据不重要，所有这里初始化为-1
	phead->next = phead->prev = phead;  //  注意双向链表的循环  
	return phead;   //  初始化返回值是  烧饼位  的地址
}

初始化之后，就是链表的插入了，老样子，先来一个辅助函数
每次插入结点都需要申请一个新的空间去储存

LTNode* BuyNode(LTDataType x)  //  借   新结点 
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));  //  获取新结点
	newnode->val = x;    //  储存需要插入的数据
	newnode->next = newnode->prev = NULL;   //  还未插入之前，都初始化为空
	return newnode;
}

链表的插入来咯，因为我们实现的是双向的循环链表，所以每次插入需要改变四个地方，新结点的前指针和后指针，插入结点之前的结点的后指针，插入结点之后结点的前指针。

看图可能更好理解，需要改变的四个地方，还有一点就是在头插和尾插时，烧饼位是不算成结点的，但链表是循环的，所以还是需要改变头结点的。比如，在头插时，需要插入在d1的前面，头结点的后面，尾插时，需要插入在头结点的前面，d3的后面，请看代码。

void LTPushBack(LTNode* phead, LTDataType x)  //  尾插
{
	assert(phead);
	LTNode* newnode = BuyNode(x);   // 获取新结点
	LTNode* pcur = phead->prev;    //  定义pcur为烧饼位的前指针也就是尾结点
	newnode->next = phead;   //  修改新结点的后指针
	newnode->prev = pcur;   //   修改新结点的前指针
	pcur->next = newnode;   //   修改尾结点的后指针
	phead->prev = newnode;  //    修改烧饼位的前指针     四个改变的地方
}
void LTPushFront(LTNode* phead, LTDataType x)  // 头插  
{
	assert(phead);
	LTNode* newnode = BuyNode(x); // 获取新结点
	LTNode* pcur = phead->next; //  定义pcur为烧饼位的后指针也就是第一个结点
	newnode->next = pcur;		//  修改新结点的后指针
	pcur->prev = newnode;		//  修改第一个结点的前指针
	phead->next = newnode;		//  修改烧饼位的后指针
	newnode->prev = phead;		//  修改新结点的前指针
}

插入部分的函数就实现了，接下来实现删除，在删除之前，需要先实现判空函数，因为如果链表为空的话，也就没必要删除了。

bool LTEmpty(LTNode* phead)   // 判空函数  
{
	assert(phead);					//    双向循环链表  
	return phead->next == phead;    //  只需要判断烧饼位的后指针是不是烧饼位即可
}

删除来咯，删除的话就不用改变四个地方，改变两个地方即可，因为删除的那个结点直接释放就行，注意删除后的链表的连接性，只需处理删除结点的前后结点就行

void LTPopBack(LTNode* phead)  // 尾删 
{
	assert(!LTEmpty(phead));   //   判断链表是否为空  加上断言
	LTNode* del = phead->prev;   //  这里是尾删   定义del为烧饼位的前结点,也就是尾结点
	phead->prev = del->prev;	//   改变烧饼位的前结点
	del->prev->next = phead;	//   改变尾结点的前结点的后指针
	free(del);  //  释放尾结点   
	del = NULL;   //  不要忘记置空  
}

void LTPopFront(LTNode* phead)  //  头删 
{
	assert(!LTEmpty(phead));      //   判断链表是否为空  加上断言
	LTNode* del = phead->next;		//  这里是头删  定义del为烧饼位的后结点  也就是首结点
	phead->next = del->next;	//  改变烧饼位的后指针  
	del->next->prev = phead;	//  改变第二个结点的前指针
	free(del);
	del = NULL;    //  释放   置空
}

删除的函数就实现好啦，接下来是任意结点之后的插入与任意结点的删除以及查找结点函数
查找函数

LTNode* LTFind(LTNode* phead, LTDataType x)   //  查找指定结点
{
	assert(phead);       
	LTNode* pcur = phead->next;   //  定义一个pcur遍历链表  
	while (pcur != phead)   //   链表循环的时候跳出循环
	{
		if (pcur->val == x)    //  如果遇到结点的值为要查找的值 
			return pcur;   //  返回结点  
		pcur = pcur->next;
	}
	return NULL;    //  没遇到就返回空指针  
}

指定位置之后插入结点，这里和头插尾插差不多，也要改变四个地方，只不过是指定结点之后插入

void LTInsert(LTNode* pos,LTDataType x)  //  在pos之后插入结点
{
	assert(pos);
	LTNode* newnode = BuyNode(x);    //  获取新结点  
	LTNode* pcur = pos->next;      
	newnode->next = pcur;    //  改变新结点的前后指针
	newnode->prev = pos;
	pos->next = newnode;   //   改变pos结点的后指针
	pcur->prev = newnode;  //   改变pos后结点的前指针
}

指定位置的删除就更简单了，和头删尾删一样的操作

void LTErase(LTNode* pos)   /// 删除节点
{
	assert(pos);
	LTNode* pcur = pos->next;
	pcur->prev = pos->prev;    //  改变要删除结点的下一个结点的前指针
	pos->prev->next = pcur;    //  改变要删除结点的前一个结点的后指针 
	free(pos);
	pos = NULL;    //  删除结点   置空  
}

删除和查找就实现完了，最后一步就是销毁链表，有借有还 ，再借不难
整个链表实现下来都是传一级指针，所以保证接口的一致性，销毁也传一级指针
想起前面说的二级指针和一级指针问题，如果这里传一级指针，只是传值调用，不会改变实参
所以在函数外部还要手动释放烧饼位。

void LTDestory(LTNode* phead)  //  销毁链表  这里使用一级指针  接口的一致性
{
	LTNode* pcur = phead->next;       // 定义结点遍历链表
	while (pcur != phead)
	{
		LTNode* next = pcur->next;  
		free(pcur);    //   逐个释放
		pcur = next;   
	}
	free(phead);  //  最后释放烧饼位   （这里是传值调用，所以不能改变实参，这一步只是象征性的操作一下）
	phead = NULL;  
}

链表的函数都实现好啦，但是会不会有bug呢，接下来我们一一测试一下函数的可行性
这里写一个打印链表函数，方便看到测试结果

void LTPrint(LTNode* phead)   //  打印测试  
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		cout << pcur->val << ' ';   //  逐步打印每一个结点
		pcur = pcur->next;
	}
	cout << endl;
}

首先测试头插和尾插函数

可以看到尾插了五个数据和头插了五个数据，顺序也是符合预期，下一个
测试头删和尾删
这里是两次尾删，是从后面开始一一删除，函数没问题

这里是两次头删，删除了10和9

头删和尾删测试完毕，下面是查找函数和删除指定结点
在6之后插入了99
删除了7

最后一步销毁链表，并且在外面将烧饼位置空

到此，整个链表的实现就结束了，手搓完毕。

总结

今天算是把链表部分全部学习完了，深入探讨了双向循环链表
自己动手实现起来还是有点麻烦，但是当写完所有的函数并且测试成功之后还是很开心的
理论和函数都实现完毕了，下一篇就是练习练习链表有关习题了。
小编持续更新中，不要走开

你敲的每一行代码，都是在为迈向美好人生做准备