数据结构之双向带头循环链表函数功能实现与详细解析-Toy模板网

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

个人主页：点我进入主页

专栏分类：C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶

C语言刷题数据结构初阶

欢迎大家点赞，评论，收藏。

一起努力，一起奔赴大厂。

1.前言

2.带头双向循环链表函数实现

3.总结

1.前言

在前面我们写过单链表，循环链表的博客，今天我主要给大家来带关于双向带头循环链表函数的功能与实现，双向带头循环链表相对于单链表，循环链表非常的容易实现，他的函数的功能和单链表，循环链表一样，如果你想要快速实现一个链表的所有功能，带头双向循环链表非常的容易，接下来让我们看看带头双向链表的奥妙把，看完你绝对会佩服写出这种结构的人。

2.带头双向循环链表函数实现

#include<stdio.h>
#include<stdlib.h>
#include <assert.h>
typedef struct ListNode {
	int data;
	struct ListNode* prev, * next;
}ListNode;
ListNode* ListCreate(int x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}
ListNode* LInit()
{
	ListNode* head = ListCreate(-1);
	head->next = head;
	head->prev = head;
	return head;
}
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next, * prev = phead;
	while (prev != phead)
	{
		free(prev);
		prev = cur;
		cur = cur->next;
	}
}
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	printf("哨兵位<=>");
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void ListPushBack(ListNode* phead, int x)
 {
	assert(phead);
	ListNode* newnode = ListCreate(x);
	ListNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
void ListPushFrount(ListNode* phead, int x)
{
	assert(phead);
	ListNode* newnode = ListCreate(x);
	ListNode* cur = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = cur;
	cur->prev = newnode;
}
void ListPopBack(ListNode* phead)
{
	assert(phead && phead->next != phead);
	ListNode* cur = phead->prev;
	cur->prev->next = phead;
	phead->prev = cur->prev;
	free(cur);
}
void ListPopFrount(ListNode* phead)
{
	assert(phead && phead->next != phead);
	ListNode* cur = phead->next;
	phead->next = cur->next;
	cur->next->prev = phead;
	free(cur);
}
ListNode* ListFind(ListNode* phead, int x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur->data != x)
	{
		cur = cur->next;
	}
	return cur;
}
void ListInsert(ListNode* pos, int x)
{
	assert(pos);
	ListNode* newnode = ListCreate(x);
	ListNode* cur = pos->prev;
	cur->next = newnode;
	newnode->prev = cur;
	newnode->next = pos;
	pos->prev = newnode;
}
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* cur = pos->next;
	ListNode* prev = pos->prev;
	free(pos);
	cur->prev = prev;
	prev->next = cur;
}
void text1()
{
	ListNode* head = LInit();
	ListPushBack(head, 1);
	ListPushBack(head, 2);
	ListPushBack(head, 3);
	ListPushBack(head, 4);
	ListPushBack(head, 5);
	ListPushFrount(head, 0);
	ListPrint(head);
	ListPopBack(head);
	ListPrint(head);
	ListPopBack(head);
	ListPrint(head);
	ListPopFrount(head);
	ListPrint(head);
	ListPopFrount(head);
	ListPrint(head);
	ListPushBack(head, 4);
	ListPushBack(head, 5);
	ListNode* cur = ListFind(head,3);
	ListPushFrount(head, 1);
	ListPushFrount(head, 0);	
	printf("%d\n", cur->data);
	ListPrint(head);
	ListInsert(head, 10);
	ListPrint(head);
}

3.总结

带头双向循环的链表非常的好，接下俩我们对顺序表和链表的存储空间，随机访问，任意位置插入或删除元素，插入，缓存利用率，应用场景进行分析文章来源地址https://www.toymoban.com/news/detail-752497.html

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低