带头双向循环链表的实现

前言

之前讲过单链表的实现，在实现的过程中，我们会发现每次删除或者在前面插入节点的时候，都要提前保存上一个节点的地址。这样做十分麻烦，所以就有了单链表的升级，双链表。今天就来实现一个带头双向循环的双链表。

带头： 指有一个哨兵位的头节点，头节点不拿来存放有效值
双向： 代表是个双向链表，一个指针存放前一个节点地址，一个地址存放后一个节点地址。
循环： 最后一个节点的下一个节点是头节点。

节点声明

刚刚提到过，双向链表是有2个指针的，一个指针指向前一个节点，一个指针指向后一个节点，还有一个来存放数据。

//存放的类型
typedef int ListValType;

//节点结构体声明
typedef struct ListNode
{
   
	ListValType val;
	struct ListNode* prve;
	struct ListNode* next;
}LSNode;
1
2
3
4
5
6
7
8
9
10
11

链表的初始化

因为我们是带哨兵头的链表，所以链表需要初始化。
初始化我们只需要开辟一个头节点，但这个节点我们不存放有效值。
而因为是循环链表，所以最后一个节点要指向第一个节点，只有一个节点时，自己指向自己。

初始化代码

//链表初始化
LSNode* ListInto()
{
   
	//创建一个节点
	LSNode* newNode = (LSNode*)malloc(sizeof(LSNode));
	//指向自己
	newNode->next = newNode;
	newNode->prve = newNode;
	
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

调试后发现它的next和prve指针都指向自己，说明初始化完成了。

尾插

那么我们就可以写个尾部插入来玩玩，我们都知道头节点的前一个地址是指向最后一个地址的。所以就可以直接找到尾节点进行插入。

//创建节点
LSNode* CreateListNode(ListValType x)
{
   
	LSNode* newNode = (LSNode*)malloc(sizeof(LSNode));
	if (newNode == NULL)
	{
   
		//空间开辟失败，不玩了
		exit(-1);
	}
	newNode->val = x;
	return newNode;
}

//尾插
void ListPushBack(LSNode* phead, ListValType x)
{
   
	//断言
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20