【c语言实现带头双向循环链表】

带头双向循环链表相比于单链表结构较复杂，但是它用代码实现起来却较容易，先来介绍它的结构。

一个节点里存上驱和下驱指针还有数据，头节点的上驱指针指向尾节点，尾节点的下驱指针指向头节点，然后他们之间进行双向互链，构成带头双向循环链表。

正是因为它这种巧妙的结构设计，不用像单链表需遍历去找上一个节点的地址，所以它在进行各种操作的时候容易实现，并且它的前增，尾增等操作的时间复杂度都是O（1）。

链表的结构体（前面有介绍）

typedef struct DList
{
	struct DList* prev;
	struct DList* next;
	int date;

}DList;

所有接口

//初始化  申请节点  尾增  前增  前删  尾删  查找  随机增  随机指定删  随机指定前删  大小  判空  释放空间  打印        
void InitDList(DList** pphead);
DList* BuySListNode(int value);
void AddDListEnd(DList* phead, int value);
void AddDListFirst(DList* phead, int value);
void DeleteListFirst(DList* phead);
void DeleteListEnd(DList* phead);
DList* FindList(DList* phead, int value);
void SpecAddList(DList* phead, DList* pos, int value);
void SpecDeleteList(DList* phead, DList* pos);
void SpecDeleteListPreve(DList* phead, DList* pos);
int SizeList(DList* phead);
int EmptyList(DList* phead);
void DistroyList(DList* phead);
void PrintDList(DList* phead);

所有接口的实现（代码处都有详细的注释）， 这里前插，尾插、前删、尾删函数都可以用随机插，随机删函数复用,释放空间时可用前删或尾删函数。还有需要注意这里进行两个节点链接的时候，先记录需链接节点的地址，防止有时候free掉找不到了，当然也有第二种方法，有一定顺序的去链接。

DList* BuySListNode(int value)//开辟新节点，并初始化
{
	DList* newnode = (DList*)malloc(sizeof(DList));
	newnode->date = value;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
void InitDList(DList** pphead)//开辟头节点，并使自己的prev,next指向自己的地址
{
	assert(pphead);
	*pphead = BuySListNode(0);
	(*pphead)->next = (*pphead);
	(*pphead)->prev = (*pphead);

}
void AddDListEnd(DList* phead, int value)
{
	assert(phead);
	DList* newnode = BuySListNode(value);
	DList* tail = phead->prev;//先纪录最后一个节点地址

	tail->next = newnode;//进行两节点的链接
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;

}
void AddDListFirst(DList* phead, int value)
{
	assert(phead);
	DList* newnode = BuySListNode(value);
	DList* first = phead->next;//记录第一个节点的地址

	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
	
}
void DeleteListEnd(DList* phead)
{
	assert(phead);
	DList* tail = phead->prev;
	DList* prev = tail->prev;//先记录倒数第二个节点的地址，然后在释放
	free(tail);
	phead->prev = prev;
	prev->next = phead;
	
}
void DeleteListFirst(DList* phead)
{
	assert(phead);
	DList* second = phead->next->next;//先记录第二个节点的位置，然后在释放
	free(phead->next);
	phead->next = second;
	second->prev = phead;
}
DList* FindList(DList* phead, int value)
{
	assert(phead);
	DList* cur = phead->next;
	while (cur != phead)//从头节点后面遍历整个链表
	{
		if (cur->date == value)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SpecAddList(DList* phead, DList* pos, int value)//在其地址前面插
{
	assert(phead);
	assert(pos);
	DList* prev = pos->prev;//先记录前面节点地址
	DList* newnode = BuySListNode(value);

	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
void SpecDeleteList(DList* phead, DList* pos)//删除所在节点的数据，调用了FindList函数查找节点地址
{
	assert(phead);
	assert(pos);
	DList* prev = pos->prev;
	DList* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}
void SpecDeleteListPreve(DList* phead, DList* pos) //删除所在节点前面的数据，调用了FindList函数查找节点地址
{
	assert(phead);
	assert(pos);
	DList* prev = pos->prev->prev;//先记录所在节点前面的前面的节点地址
	free(pos->prev);
	pos->prev = NULL;
	prev->next = pos;
	pos->prev = prev;
}
int SizeList(DList* phead)
{
	assert(phead);
	int count = 1;//头节点也算一个节点
	DList* cur = phead->next;//从头节点后面遍历整个链表
	while (cur != phead)
	{
		count++;//计数器
		cur = cur->next;
	}
	return count;
}
int EmptyList(DList* phead)
{
	assert(phead);
	if (phead->next == phead && phead->prev == phead)
	{
		return 0;//为空
	}
	else
	{
		return 1;//不为空
	}
}
void DistroyList(DList* phead)
{
	assert(phead);
	DList* cur = phead->next;
	while (cur != phead)//遍历整个链表进行释放

本站声明：
1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享；

2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关；

3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关；

4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除；

5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。