带头双向循环链表的增删查改

之前的话，我给大家实现过单链表的增删查改，但是单链表的结构在实际应用中的可以说根本用不到，所以呢，今天我给大家带来了带来带头双向循环链表的增删查改，看完双向带头循环链表的实现，你们会发现单链表有很多不足的地方。

结构体的设计如下:

该结构体的里面是有两个指针的，一个prev和一个next，next存放下一个指针的地址，而prev的话存放上一个指针的地址，data就是我们要存放的数据类型

创建返回链表的头结点

LTNode* ListInit()
{
    
	LTNode* head = (LTNode*)malloc(sizeof(LTNode));
	head->next = head;
	head->prev = head;
	return head;
}

这里呢，我并没有跟之前一样写一个初始化的函数，而是创建一个头节点返回，当然这里的头节点是不存储数据的，因为我们这个结构是带头双向循环链表，我们先malloc一个节点，将head指向它，这里需要注意的是，我们需要将head->next和head->prev都指向自己，至于为什么，我后面会和大家讲。

双向链表的打印

void ListPrint(LTNode* phead)
{
    
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
    
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

这里呢，我先给大家看一下带头双向循环链表的结构
如下:

这里的head其实就是我们第一个哨兵位的头节点，紧接着后面才是我们存储的数据，所以这里要将该链表打印的时候，我们应该先拿到哨兵位的头节点的下一个指针，再进行打印。
这里我断言一下因为phead是不能为空的，然后将cur指向phead->next，
之后循环打印链表的时候，我们要注意循环条件，循环条件应该是cur!=phead，当cur==phead的时候，就说明该链表又回到了哨兵位的头节点，数据也就全部打印完了。

双向链表尾插

void ListPushBack(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;
}

我先给大家分析一下尾插的逻辑
如图:

图中tail就是还没有完成链接时候的尾节点，newnode就是需要尾插的节点，
phead就是头节点，我们首先要将尾节点给找到，而phead->prev就是tail也就是尾，之后要将tail->next指向newnode，newnode->prev指向tail，这时候nenode就变成了新的尾节点了，最后再将newnode->next指向phead，phead->prevz指向newnode，但是如果链表里只有一个哨兵位的头节点，我们的代码是否还能正常运行呢?答案是肯定的，因为当只有一个哨兵位的头节点的时候，tail其实就是自己，大家可以试着去画图理解一下，会发现能实现尾插，这也就是我一开始为什么要让prev和next都指向自己，另外因为有一个带哨兵位的头节点，所以我们是不需要传二级指针的，因为哨兵位的头节点并不需要改变，我们只需要改变它里面的头节点即可。

双向链表尾删

void ListPopBack(LTNode* phead)
{
    
	assert(phead);
	assert(!ListEmpty(phead));
	LTNode* tail = phead->prev;
	LTNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
}

尾删这里是需要多加一个判断的，因为当链表只剩一个哨兵位的头节点就不能再删除了，这里我写了一个函数判断链表是否为空，再用assert断言，当然你们也可以用if语句去判断，当phead->next==phead的时候就直接return即可。

如图，我们首先要找到尾节点tail，和尾的前一个节点prev，然后将phead和prev给链接起来，让prev成为新的尾节点，我们需要将prev->next指向phead，phead->prev指向prev，再将tail这个节点给释放，最后将tail给置成空，我们的尾删就完成了，如果说里面除去哨兵位的头节点只有一个的话，我们的代码也是能实现的，这就是我一开始为什么要让prev和next都指向自己，这样的话我们就不需要去判断特殊情况。

双向链表头插

void ListPushFront(LTNode* phead, LTDataType x)
{
    
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* next = phead->next;

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

头插我们需要先创建一个节点newnode，然后保存phead的下一个节点next，再让newnode和phead给链接起来，即phead->next指向newnode，newnode->prev指向phead，这样newnode就成为了新的头节点，但是phead和newnode链接的同时会和next这个节点断开，所以我们还需要将newnode和next节点链接起来，将newnode->next指向next，next->prev指向newnode，这里的话也是不需要去判断特殊情况的。

双向链表头删

void ListPopFront(LTNode* phead)
{
    
	assert(phead);
	assert(!ListEmpty(phead));
	LTNode* frist = phead->next;
	LTNode* next = frist->next;
	phead->next = next;
	next->prev = phead;
	free(frist);
	frist = NULL;
}

头删和尾删一样都需要判断链表是否只剩一个哨兵位的头节点，当只剩一个哨兵位的头节点就不能再删除了。

我们需要保存phead后一个节点frist，再将frist的后一个节点next也保存起来，因为frist是头节点，是我们需要释放的节点，但是如果释放了first节点，就找不到它后面的节点了，phead也就没办法链接到新的头节点了，之后我们需要将phead和next给链接起来，将phead->next=next，next->prev指向phead。

双向链表查找

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

带头双向循环链表的查找和之前单链表一样，查找附带这修改的功能，因为外面可以拿到节点的指针，通过节点的指针去修改里面存储的数据。我们只需要遍历一遍链表如果找到与相等的值则返回该节点，如果没找到就返回NULL。

最后，带头双向循环链表的话，我就没办法找一些OJ题给大家分享了，因为它的结构相对来说是比较完美的，不适合用来出题，虽然带头双向循环链表结构比较复杂，但是大家和单链表的增删查改对比一样，从实现的角度单链表其实更麻烦，感谢大家观看，喜欢的记得点赞收藏加关注哦!