双向循环带头链表

上次我们学习了单链表，但是在自己实现的时候我们不难发现单链表其实不适合存储数据，对于头删头插它的效率可以，但是对于其他的功能来说，这显得太复杂。每次都要遍历一次，而每遍历一次都是要消耗时间的，所以单链表的效率不高。

下面的双向循环带头链表就解决了这个问题：
还是像之前的单链表一样，我们先看看接口：

ListNode* LTInit();
ListNode* BuyNode(LTDataType x);
void LTPrint(ListNode* phead);
void LTPushFront(ListNode* phead, LTDataType x);
void LTPushBack(ListNode* phead, LTDataType x);
void LTPopFront(ListNode* phead);
void LTPopBack(ListNode* phead);

ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

// 双向链表销毁
void ListDestory(ListNode* phead);
//链表的数据个数
size_t ListSize(ListNode* phead);
//判断链表是否为空
bool IsListEmpty(ListNode* phead);

那么首先我们要创建结构体来表示每一个节点：

这样创建之后初始化就没有单链表那么简单了，这是我们可以用一个函数去实现初始化：
 

ListNode* LTInit()//链表初始化
{
	ListNode* guard = (ListNode*)malloc(sizeof(ListNode));//创建哨兵位的头节点
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	guard->next = guard;
	guard->prev = guard;
	return guard;
}

 根据我们之前学单链表我们可以知道头插头删是可以不需要单独写的，这次就主要把任意位置的插入和删除写出来直接调用函数就可以解决头插头删的问题了：

在这之前我们要找到位置并创建节点：

ListNode* BuyNode(LTDataType x)//创建节点
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");//防止创建失败
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

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

对于查和改其实是一回事，只要查到了改就很简单了：

下面就演示了修改的操作：

 找到数据了，之后就可以在任意位置插入删除了，因为双向循环带头链表是很好找前一个的，所以我们在插入数据时一般都是插入在当前位置的前一个：

void ListInsert(ListNode* pos, LTDataType x)//任意位置之前的插入
{
	assert(pos);
	ListNode* prev = pos->prev;//记录pos之前的位置
	ListNode* newnode = BuyNode(x);
	//建立链接关系
	newnode->prev = prev;
	newnode->next = pos;
	prev->next = newnode;
	pos->prev = newnode;
}

删除也是很简单：

void ListErase(ListNode* pos)//任意位置的删除
{
	assert(pos);
	assert(!IsListEmpty(pos));
	ListNode* prev = pos->prev;//记录前一个位置
	//建立前一个和后一个的链接
	prev->next = pos->next;
	pos->next->prev = prev;
	free(pos);//删除节点
	pos = NULL;//这里置空无效，因为这里是零时变量，应该由使用者置空
}

在完成了这几个函数之后头插头删也变得异常简单：

void LTPushFront(ListNode* phead, LTDataType x)//头插
{
	assert(phead);
	ListInsert(phead->next, x);//因为这个是在pos位置之前插入，所以要传第一个
}

void LTPushBack(ListNode* phead, LTDataType x)//尾插
{
	assert(phead);
	ListInsert(phead, x);//头的前面就是尾
}

void LTPopFront(ListNode* phead)//头删
{
	assert(phead);
	assert(!IsListEmpty(phead));
	ListErase(phead->next);//不能删除带哨兵位的头节点
}

void LTPopBack(ListNode* phead)//尾删
{
	assert(phead);
	assert(!IsListEmpty(phead));
	ListErase(phead->prev);//头的前一个就是尾就是pos的位置
}

这里删除的时候用一个函数去判断链表是否为空：

bool IsListEmpty(ListNode* phead)//判断链表是否为空
{
	assert(phead);
	return phead->next == phead;//如果为相等的话，那么就为空，返回真
}

在数据都插入删除后我们可以通过实现打印函数，更直观的观察：

void LTPrint(ListNode* phead)//打印数据
{
	assert(phead);
	ListNode* cur = phead->next;
	printf("phead<=>");
	while (cur != phead)//因为是循环链表，所以最后的条件应该是不等于头节点结束
	{
		printf("%d<=>",cur->data);
		cur = cur->next;
	}
	printf("\n");
}

如果我们想知道存储了多少数据，我们也可以通过遍历一次来求出数据的个数：

size_t ListSize(ListNode* phead)//计算链表数据的个数
{
	assert(phead);
	ListNode* cur = phead->next;//头节点不算数据
	size_t n = 0;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}
	return n;
}

最后我们使用完后要记得销毁链表，不然会导致内存泄漏：

void ListDestory(ListNode* phead)//链表的销毁
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode*  next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;//这里不起作用，要销毁的那个人自己置空，这里保证了接口参数的一致性
}

在实现双向循环链表的时候能明显感觉到其存储数据的高效，很多功能十分容易就能实现

在对比顺序表以及链表的时候，我们不能说链表就一定优胜顺序表，顺序表有着一个非常大的优势，那就是随机访问，这个优势就是顺序表不能被链表取代的原因。

顺序表的缓存利用率更高：