双向带头循环链表的实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了双向带头循环链表的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.学习第一步：

当我们要学习和了解一个事物时，我们要做的第一步便是对这个事物有一个体的的了解。现在我们要学习双向带头循环链表的第一步也是这个，我们现在先来了解一下这种链表的结构----

就像该图所呈现的那样，双向循环链表就是长这样。但是你可千万不要将head当成head。 这里的head是一个哨兵位的头!

二，实现带头双向循环链表

在上面的介绍中，相信在你的脑海中已经有了带头双向循环链表的样子了。现在我们就来实现一下吧。

2.1：链表的诞生（链表初始化）

链表的初始化的目的就是要将带头双向循环链表的头（head)给搞出来。当然，在此之前还是要有一个链表结点的结构。

结构：

typedef int datatype;
 typedef struct ListNode{
	 datatype data;
	 struct ListNode* next;
	 struct ListNode* prev;

}ListNode;

第一个功能的实现——初始化链表：InitList()

void InitList(ListNode* head)
{
	head->next = head;
	head->prev = head;
	head->data = -1;
}

当然，在初始化操作之前还得先创建一个节点传进InitList()中。这一步操作是在test.c文件中的。

void test1()
{
	ListNode* list =(ListNode*) malloc(sizeof(ListNode));//创建节点
	InitList(list);

}
int main()
{
	test1();
	return 0;
}

第二个功能的实现——尾插：pushBack()

相对于单链表来说，简直小菜一碟！

void pushBack(ListNode* head,datatype x)

{
    assert(head);
	ListNode* newnode = Buynewnode(x);
	ListNode* tail = head->prev;

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

	newnode->next = head;
	head->prev = newnode;

}

第三个功能的实现——ListPrint(Listnode* head)

这个打印函数实现起来那就更加得心应手了，只不够这个函数的终止条件是比较特殊的。它的终止条件是当指针走到哨兵位的头结点时就停止。当然这个指针的起始位置是哨兵位的下一位！

void Listprint(ListNode* head)
{
    assert(head);
	ListNode* cur = head->next;
	while (cur != head)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
	
}

第四个功能的实现——头插

头插的意思就是生成一个新的节点然后添加到哨兵位的头节点的后面变成新的头节点。

void pushFront(ListNode* head, datatype x)
{
    assert(head);
	ListNode* newnode = Buynewnode(x);
	ListNode* next = head->next;

	head->next = newnode;
	newnode->prev = head;

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

第八个功能——中间插入

这个函数是个能将头插，尾插两种功能联合起来实现的函数（改一下传入的参数就行了）。

先找到指定的节点：

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

文章来源地址https://www.toymoban.com/news/detail-447003.html

在指定元素的后面插入：

void ListInsert(ListNode* pos, LTDataType x)//中间插入，在pos的后面插入一个节点
{
	assert(pos);
	ListNode* newnode = Buynewnode(x);
	ListNode* next = pos->next;

	pos->next = newnode;
	newnode->prev = pos;

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

第五个功能的实现——尾删

尾删尾删就是要把链表尾部的节点给删除掉，在这个带头双向循环链表里实现这个功能是十分简单的！并且时间复杂度为O(1)效率特别高！

代码：

void popBack(ListNode* head)
{
	assert(head);
	ListNode* del = head->prev;//记录一下要删除的尾节点
	ListNode* tailFront = del->prev;//找到尾结点的前一个节点

	tailFront->next = head;
	head->prev = tailFront;

	free(del);
	del = NULL;
}

第六个功能的实现——头删

头删的操作与尾删差不多，只不过删尾变成了删头。

void popFront(ListNode* head)
{
	assert(head);
	ListNode* del = head->next;
	ListNode* next = del->next;

	head->next = next;
	next->prev = head;

	free(del);
	del = NULL;
}

第七个功能——中间删除

中间删除是包含头删与尾删的其实，假如你要将头删与尾删的功能用一个函数进行实现的话那就可以实现一个中间删除函数。

void ListErase(ListNode* pos)//中间删除，删除pos后面的节点,但是不能删除哨兵位的头
{
	assert(pos);
	ListNode* del = pos;

	ListNode* Frontnode = del->prev;
	ListNode* next = pos->next;

	next->prev = Frontnode;
	Frontnode->next = next;

	free(del);
	del = NULL;
}

当你要变成一个头删函数时，这个中间删除的函数的参数改变一下就行了。

ListErase(head->next);//头删

ListErase(head->prev);//尾删

但是当你要删除一个既不是头也不是尾的节点时，你就要再弄一个查找函数。

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

用这个函数定位到你要删除的元素，然后再将其删除！但是返回空指针的时候是不能进行删除的！

最后一个功能——销毁链表

因为你的链表的节点是malloc出来的，所以你要在用完以后将其销毁来避免内存泄漏。

void ListDestory(ListNode* head)
{
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	while (cur !=pHead) {
		free(cur);
		cur = next;
		next = cur->next;
	}
	printf("销毁成功!\n");
}

到了这里，关于双向带头循环链表的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！