数据结构之带头双向循环链表

前言： 前面我们已经学习了顺序表和单链表，那么我们今天来学习数据结构中的另外一个线性表——带头双向循环链表。

带头双向循环链表：

头结点：带头也就是我们常说的“哨兵位”，头结点其中不存放任何的数据。哨兵位的存在可以帮助我们更好的进行链表的增删操作。

双向：我们的单链表是单向的，只能从前访问到尾，而我们双向的则可以从前访问后一个，也可以从后访问前一个，但是我们的单链表不具备这样的功能。

定义双向链表：

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

双向链表意味着我们要定义两个指针，既可以从前访问后一个，又可以从后访问前一个。

接口的实现：

//初始化
LTNode* LTInit();
//打印链表
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
// pos
void LTInsert(LTNode* pos, LTDataType x);
// pos
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

初始化链表：

LTNode* CreateLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
LTNode* LTInit()
{
	LTNode* phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

CreateLTNode这个函数我们用来创建一个新的节点，因为我们的链表是双向的，所以我们初始化只要头结点的下一个指向它自己，它的前一个指向它自己就可以了。

打印链表：

void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("哨兵位");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

尾插：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = CreateLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

我们的尾节点的下一个指向我们要插入的新节点，而我们的新节点的上一个节点指向尾节点，我们的现在的尾节点为newnode，再使得它的下一个节点指向哨兵位，哨兵位的前一个节点指向newnode。

尾删：

void LTPopBack(LTNode* phead)
{
	assert(phead);
	// 空
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

我们这里保存我们的尾节点和我们尾节点的上一个节点，再释放掉尾节点，最后让哨兵位的下一个节点指向我们的tailprev，tailprev的上一个节点指向哨兵位就可以了。

头插：

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);
	LTNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

我们定义两个指针，头结点的下一个为first，我们的头结点下一个节点指向新节点，我们的新节点的上一个节点指向头结点，我们的新节点的下一个节点指向first节点，first节点的上一个节点指向新节点。

头删：

void LTPopFront(LTNode* phead)
{
	assert(phead);
	// 空
	assert(phead->next != phead);
	LTNode* first = phead->next;
	LTNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;
}

我们同样定义多个指针来保存节点，我们让头结点的下一个节点指向second节点，second节点的上一个节点指向头结点，最后再释放掉first节点并且置为空就可以了。

查找链表：

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

pos前插入：

// 在pos前面的插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = CreateLTNode(x);
	// posprev newnode pos
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

这里同样的方法，相比之下比较简单，但是我们的pos的位置是头结点呢，那是不是就相当于尾插了呢？看到下图所示：

那我们尾插的代码是不是就可以换一种写法了呢：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTInsert(phead, x);
}

我们这里调用pos前插入的函数，而我们的位置为头结点，这样就更加简单实现了尾插。

删除pos位置：

// 删除pos位置
void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posNext = pos->next;
	LTNode* posPrev = pos->prev;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
	//pos = NULL;
}

删除pos位置的逻辑同样简单，只需要我们多定义几个指针来保存节点，在通过链接最后在释放pos就可以了，这里我们同样利用这个函数来进行尾删。

void LTPopBack(LTNode* phead)
{
	assert(phead);
	// 空
	assert(phead->next != phead);
	LTErase(phead->prev);
}

销毁链表：

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;
}

我们这里只需要遍历一遍，使得我们的节点不等于头结点，再保存下一个节点，然后释放掉当前节点，最后当我们的节点为头结点再释放掉头节点就可以了。

带头双向循环链表相对于其他的链表而言还是比较简单的，如果大家有所收获的话，就给我点点赞吧，感谢大家的支持！