【大型数据结构连续剧之----带头双向循环链表】带你通透这傲娇的结构

前言

---

•  输入是学习的本质,输出是学习的手段。
•  分享每一次的学习，期待你我都有收获。
•  欢迎关注点赞⭐️收藏✉评论，共同进步！
•  “要足够优秀，才能接住上天给的惊喜和机会”
•  博主水平有限，如若有误，请多指正，万分感谢！

• 一、带头双向循环链表的结构优势
• 二、各个接口函数的实现：
• • • ☁️增容--开辟新节点
    • ☁️初始化头节点
    • • ①方法 1
      • ②方法 2
    • ☁️头插
    • ☁️尾插
    • ☁️头删
    • ☁️尾删
    • ☁️修改节点数据
    • ☁️查找节点
    • ☁️在任意节点前插入，单链表如何？
    • ☁️删除任意节点
    • ☁️打印链表

为什么说它傲娇呢，因为它在逻辑结构中表现得很复杂，让人不敢靠近。 但其实真正写起代码来，对大家伙子们可以说是百般照顾！那叫一个顺畅！

当我第一次看到双向循环链表的时候，也不禁皱了皱眉头，相比于无头单向非循环链表，它的逻辑结构看上去似乎更加复杂，但其实，这也正是带头双向循环链表的结构优势：

它的每一个节点之间都是存在相互联系的

当我们需要进行插入、删除、移动的操作时，我们不需要像单向链表那样，从第一个节点开始遍历直到我们要的前驱节点。只要调用指向前驱的指针，就能找到我们要的前驱节点了。

因此，带头双向循环链表其实是一个没有缝隙的数据结构，在实现代码时，我们不需要像构造单链表g各个接口函数时，谨慎地去考虑头节点等是否存在特殊情况。带头双向循环链表，它的代码实现简洁明了，这正是他的结构优势。

结构体类型定义以及头节点的创建：

ListNode* plist=NULL;   //创建头节点

typedef struct ListNode ListNode;

typedef int ListDataType;

struct ListNode
{
	ListDataType val;
	ListNode* pre;
	ListNode* next;
};

双向链表最常见的包括这些接口：（先介绍）

//增容 开辟新节点

ListNode* ListMalloc(ListDataType x);


//初始化头结点。

ListNode* ListInit();


//头插

void PushFront(ListNode* phead);


//尾插

void PushBack(ListNode* phead);


//头删

void PopFront(ListNode* phead);


//修改节点。

void ListModify(ListNode* pos,ListDataType x);


//查找节点

ListNode* ListFind(ListNode* phead);


//在任意一个节点前插入

void ListInsert(ListNode* phead,ListDataType);


//打印

void ListPrint(ListNode* phead);

//增容 开辟新节点
ListNode* ListMalloc(ListDataType x)
{
	ListNode* str = (ListNode*)malloc(sizeof(ListNode));
	str->val = x;
	str->pre = NULL;
	str->next = NULL;
}

初始化头节点，或者说是"初始化头指针" 更为恰当，是将头指针指向一个节点，

该节点就称为头节点。

头结点又叫哨兵位，不做数据存储使用，而是为了操作方便，当链表中存在哨兵位时，链表的有效数据是从第二个节点开始的。

需要注意的是：既然初始化头结点需要改变头指针的指向，要改变指针中存储的地址，有多种方法：

以返回值的形式让头指针plist接收，通过给plist赋值的形式改变plist的指向。

//初始化头节点 无->有

ListNode* ListInit()
{
	ListNode* phead = ListMalloc(0);
	phead->next = phead;
	phead->pre = phead;
}

在函数形参中定义二级指针用于接收头指针plist的地址。

通过访问plist的地址去改变plist所存储的内容——地址。

两种方法都可以，视个人习惯而定。

//二级指针
void ListInit(ListNode** phead)
{
	*phead = ListMalloc(0);
	(*phead)->pre = *phead;
	(*phead)->next = *phead;

}

头插时可以加个断言避免phead为空的情况。

//头插

void PushFront(ListNode* phead,ListDataType x)
{
	assert(phead);
	ListNode* next = phead->next;//哨兵位的下一个节点才是第一个有效节点
	ListNode* data = ListMalloc(x);//开辟一个新节点,用于头插
	data->pre = phead;
	data->next = next;
	phead->next = data;
	next->pre = data;
	
}

尾插也加一个断言。

void PushBack(ListNode* phead,ListDataType x)
{
	assert(phead);
	ListNode* tail = phead->pre;//最后一个节点的位置
	ListNode* data = ListMalloc(x);//开辟一个新节点，用于尾插
	tail->next = data;
	data->pre = tail;
	data->next = phead;
	phead->pre = data;
	
}

头删要注意的是：

当链表只剩一个头节点的时候，不能再继续删除了，若是把头节点也删了，并且置为空指针，链表将不复存在。

因此我们不仅要断言判断头节点是否为空，还要判断头节点的指向后继的指针是否指向了自己，如果是，就证明该链表中只剩头节点。

//头删

void PopFront(ListNode* phead)
{
	
	assert(phead);
	assert(phead->next!=phead);  //只剩头节点了，不能把头节点给删了
	ListNode* first = phead->next;  //第一个节点
	ListNode* second = first->next; //第二个节点
	
	free(first);
	phead->next = second;
	second->pre = phead;

	first = NULL;
}

尾删同样也要断言头节点不能被删。

//尾删

void PopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next!=phead);  //只剩头节点了，不能把头节点给删了
	ListNode* First = phead->pre;//最后一个节点的位置
	ListNode* Second = First->pre;//
	phead->pre = Second;
	Second->next = phead;
	
	free(First);
	First = NULL;

}

//修改节点数据

void ListModify(ListNode* pos,ListDataType x)
{
	assert(pos);
	pos->val = x;
}

ListNode* ListFind(ListNode* phead,ListDataType x)
{
	//从第一个有效节点开始查找
	ListNode* cur = phead->next;
	while (cur != phead)  //循环链表走到最后的依据不是NULL，而是头节点点
	{
		if (cur->val == x)
		{
			return cur; //找到了，返回该节点地址
		}
		cur = cur->next;
	}
	return NULL; //没找到，返回NULL

}

//先找节点，有这个节点再进行插入。

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	assert(pos != pos->next);
	ListNode* pre = pos->pre; //马上就找到了pos的前一个节点
	ListNode* newnode = ListMalloc(x);
	pre->next = newnode;
	pos->pre = newnode;
	newnode->pre = pre;
	newnode->next = pos;
	
}

单链表当然也可以实现在 某一个节点（假设A节点）前插入节点，但是因为它是单向的，无法记住前一个节点的地址，因此在找到A节点后，我们需要重新再从第一个有效节点开始，遍历链表，直到找到A节点的前一个节点，时间复杂度为O(n)。

而如果在双向链表的环境下，只要找到A节点，A节点立刻就可以找到它的前一个节点。

//删除任意节点

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* First = pos->pre;
	ListNode* Second = pos->next;
	First->next = Second;
	Second->pre = First;
	free(pos);
}

//打印

void ListPrint(ListNode* phead)
{

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
}