＜数据结构与算法＞带头双向循环链表_判断循环双向链表是否为空 prie指向自己

目录

前言

一、链表的分类

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

1.结构体创建

2.LTInit 链表初始化

3.LTPrint 打印

4.LTEmpty 判断是否为空 

5.LTPushBack 尾插

6.LTPopBack 尾删

7.LTPushFront 头插

8.LTPopFront 头删 

9.LTInsert 插入

10.LTFind 查找

11.LTErase 删除

12.LTDestroy  释放

总结

前言

1. 尾next指向哨兵位的头
2. 哨兵位的头的prev指向尾

---

一、链表的分类

1.单向或者双向

2.带头或者不带头 (哨兵位不储存有效数据)

3.循环或者非循环

排列组合共有八种结构，虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：  

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

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

1.结构体创建

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

2.LTInit 链表初始化

• 创建头节点（哨兵位）使其prev与next均指向其本身

双向链表相较于单链表需要初始化，因为单链表只需要创建phead结构体指针，不需要单独写一个函数去初始化，在主函数使用时创建即可，而双向链表需要初始化创建一个头节点即——哨兵位节点使其prev与next均指向其本身。

//初始化
LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}

3.LTPrint 打印

• 循环至哨兵位结束打印

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

4.LTEmpty 判断是否为空 

bool LTEmpty(LTNode* phead)
{
	assert(phead);
 
	/*if (phead->next == phead)
	{
		return true;
	}
	else
	{
		return false;
	}*/
 
	return phead->next == phead;
}

5.LTPushBack 尾插

因为带头双向循环链表的特点 ：

1. 尾next指向哨兵位的头
2. 哨兵位的头的prev指向尾

• 我们不需要再去循环找尾节点，phead->prev就是尾节点，接下来创建新节点，将其新节点与哨兵位prev与next指向改变即可。
• 因为有哨兵位，所以我们在链接时不需要判断链表是否为空，大大方便代码
• 因为有哨兵位，我们不会改变头节点的值，所以不需要传二级指针，直接链接即可

//新节点初始化
LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		//return NULL;
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;
 
	return node;
}
 
 
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);//断言
 
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;//找尾节点
 
	//链接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

6.LTPopBack 尾删

由于双向循环链表的结构使得各函数基本没有难点，很容易编写，这里就不多赘述

• 需要注意的一点是，当链表只剩哨兵位时就不可以再删了，需要断言，我们将该断言独立分装为一个函数LTEmpty

//判断链表是否为空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
 
	/*if (phead->next == phead)
	{
		return true;
	}
	else
	{
		return false;
	}*/
 
	return phead->next == phead;
}
 
 
//尾删
void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
 
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	tail = NULL;
}

7.LTPushFront 头插

•  先后再前

//头删
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* newnode = BuyListNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
 
	newnode->next = first;
	first->prev = newnode;
 
    //不能随便换顺序
	//newnode->next = phead->next;
	//phead->next->prev = newnode;
 
	//phead->next = newnode;
	//newnode->prev = phead;
}

8.LTPopFront 头删 

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* tail = phead->next->next;
	LTNode* cur = phead->next;
	phead->next = tail;
	tail->prev = phead;
	free(cur);
	cur = NULL;
 
	/*LTErase(phead->next);*/
}

9.LTInsert 插入

//pos前插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	// prev newnode pos
 
	prev->next = newnode;
	newnode->prev = prev;
 
	newnode->next = pos;
	pos->prev = newnode;
}

10.LTFind 查找

• 跟打印函数一样，遍历链表
• 如果查找不到就返回NULL

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

 11.LTErase 删除

• 删除函数搭配Find函数使用
• 置空没用，可以传二级指针，也可在主函数内置空

void LTErase(LTNode* pos)
{
	assert(pos);
 
	LTNode* p = pos->prev;
	LTNode* n = pos->next;
 
	p->next = n;
	n->prev = p;
	free(pos);
	//pos = NULL;
}

12.LTDestroy  释放

void LTDestroy(LTNode* phead)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
 
	free(phead);
	//phead = NULL;
}

---

总结

        显而易见，双向链表书写简单，没有在单链表时的诸多难点。在链表中，有八种分类，但我们绝大多数使用两种，无头不循环单向链表、带头循环双向链表，其中带头循环双向链表基本没有题，因为结构完美没有什么可以考的点，而无头不循环单向链表频繁出现在题目中，考察增删查改操作细节。

        带头循环双向链表与顺序表相较而言，双向链表优势非常大，但是顺序表会因此被淘汰了吗？不然，当我们在查找、排序时我们需要下标来指引，这时链表就不是很方便了，所以，我们所学的每个结构都有它独特之处，没有绝对的完美。

 最后，如果小帅的本文哪里有错误，还请大家指出，请在评论区留言（ps：抱大佬的腿），新手创作，实属不易，如果满意，还请给个免费的赞，三连也不是不可以（流口水幻想）嘿！那我们下期再见喽，拜拜！