如何实现双向循环链表

引言

双向带头循环链表是一种常见的数据结构，它具有双向遍历的特性，并且在表头和表尾之间形成一个循环。本文将深入探讨双向带头循环链表的结构、操作和应用场景，帮助读者更好地理解和运用这一数据结构。

本篇博客将以图表和代码相结合的方式手撕双向带头循环链表，代码使用C语言进行实现。

1. 结构的定义

双向带头循环链表由多个节点组成，每个节点包含数据域和两个指针域，分别指向前驱节点（prev）和后继节点（next）。在链表的表头和表尾之间会形成一个循环，使得链表可以从任意节点出发进行正向或反向的遍历。

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

通过代码可以感受到，每一个链表节点都包括一个prev和一个next（除了哨兵节点），整体结构的示意图如下：

2. 基本操作

2.1 准备操作

2.1.1 创建新节点

ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

每个节点都应该具备data，next，prev这三个结构体成员，结构的定义在上文已经进行了描述，所以在创建新节点中直接用ListNode*类型进行新节点的创建。参数x表示要在新节点上插入的数据，在创建新节点后对新节点的成员进行初始化，最后返回ListNode*类型的newnode。

2.1.2 初始化链表

ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

在刚开始的时候需要对链表进行初始化。我们要实现的是一个双向带头循环链表，所以在初始化的时候使哨兵节点的next指向自己，prev指向自己，这样的结构对后面对链表的操作会方便很多，提供了很大的便利。

2.2 遍历操作

2.2.1 打印链表

void ListPrint(ListNode* phead)
{
	assert(phead);

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

打印链表不仅可以实现最后链表结果的输出，也可以让我们在进行链表代码书写的时候进行检查所写接口是否有误。

在实现打印链表的时候我们先用一个assert断言来进行判断，如果phead使空的话就会报错停止运行，因为至少要保证有一个表头，要不然无法组成链表。

我们使用一个指针cur来进行访问链表，初始化cur指向phead的next，这样就指向了第一个节点，从第一个节点开始遍历，之后用while循环来进行遍历，每次循环打印当前cur的data，使cur指向cur的next，也就指向了下一个节点。终止的条件是：当cur指向phead的时候终止循环。

2.2.2 查找数据位置

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

		cur = cur->next;
	}

	return NULL;
}

首先用assert断言确保该链表不是空的，以保证可以正确查询。定义一个指针cur指向哨兵节点的next（第一个节点），然后循环遍历，直到cur对应的data为要查找的x值的时候停止循环，返回存储x的节点，如果未找到则返回NULL。通过此操作即可找到要查找的数据的位置。

2.3 插入操作

在表头插入的时候有链接新节点的顺序需要注意，有以下两种，第一种为指针方法忽视链接顺序，第二种为直接链接新节点，需要注意链接顺序。

2.3.1.1 在表头插入新节点（first指针）

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);

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

2.3.1.2 在表头插入新节点（顺序链接）

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

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

以上为两个表头插入接口函数，明显的区别就是第一种使用first进行保存表头的next，之后在连接的时候使用first就可以进行正常链接。第二种中直接进行链接，但是这种需要注意链接的顺序，因为程序的编译是从上向下进行编译，所以在链接时的顺序不当可能使本该链接的地址被修改覆盖，造成错误的链接，使插入节点新失败。

2.3.2 在表尾插入新节点

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);

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

由于哨兵节点的结构有前驱节点和后继节点，所以在循环带头双向链表中哨兵节点的前驱节点就是最后一个节点的后继节点。我们用tail表示链表的最后一个节点，使tail指向表头的前驱节点，这样就可以快速定位到最后一个节点的next，以便于用来拼接新节点。之后就是使表头和当前的tail与新节点的前驱节点和后继节点进行拼接。

2.3.3 在指定位置插入新节点

// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	// prev newnode pos
	prev->next = newnode;//pos前的节点的next
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

用该接口在pos位置前插入新节点。因为NULL没有前后两个指针域，为了避免pos是NULL所以我们使用assert断言进行判断，避免出错。定义一个prev表示pos前的节点，然后用prev链接newnode，再用newnode链接pos，这样就完成了在pos前插入数据了。

2.4 删除操作

2.4.1 删除表头节点

void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;

	free(first);
	first = NULL;
}

该接口中一共使用了两次assert断言：

1. assert(phead);
2. assert(phead->next != phead);

第一个assert用来放置表头为NULL，第二个assert是避免链表不存在数据还进行删除，因为当链表中只存在哨兵节点的时候它的next是指向它自己的，所以使用的条件是phead的next不等于phead。

因为我们是从表头删除节点，所以我们可以先通过哨兵节点找到第一个节点，然后再找到第二个节点。我们的目的是将第一个节点删除，所以我们先定义一个指针first然后用first先暂时存贮第一个节点，然后通过first找到第二个节点，最后再用phead的next与第二个节点进行链接（free掉first节省空间）。如此便实现表头删除节点的接口。

2.4.2 删除表尾节点

void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);

	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;

	free(tail);
	tail = NULL;
}

该接口的两个assert和上方表头删除节点的原理相同，不做过多讲解。

循环链表的表尾就是表头的prev，所以很简单就可以将tail表示出来。再定义一个prev指针用来存储要删除的尾的前一个节点位置。在完成准备工作后我们使用prev的next跳过tail直接指向phead，然后在将phead的prev指向prev。这样就完成了表尾节点的删除，最后用free将之前的表尾节点释放掉就更完美啦！

2.4.3 删除指定位置节点

// 删除pos位置的值
void ListErase(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
}

该节点用来删除指定位置的节点。

首先使用assert断言保证该位置不是NULL，可以真实进行修改。

例如说，我们要删除d2节点：

按照代码逻辑d2就是传入的参数pos，现在我们定义一个指针prev指向d2的prev，也就是d1，再定义一个指针next指向d2的next，也就是d3。 这样我们就拥有了prev和next两个分别指向目标节点前后节点的指针，然后通过这两个这两个指针将d1和d3进行链接就完成了删除d2的操作，当然，最后将d2给free掉就更完美啦~

通过本文的介绍，我们对双向带头循环链表有了更深入的了解，包括其结构、基本操作、应用场景以及示例代码。双向带头循环链表作为一种重要的数据结构，在实际开发中有着广泛的应用，希望本文能够帮助读者更好地理解和应用这一数据结构。