系列文章目录

前言

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

一、链表的概念及结构

1.链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

2.双向带头循环链表结构

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

1.定义链表节点struct ListNode

数据域data,指针域中包括指向前面节点的前驱指针prev，指向后面的后驱指针next
代码如下：

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}; 

2.创建链表节点BuyListNode函数

代码如下：

struct ListNode* BuyListNode(LTDataType x)
{
	struct ListNode* Node = (struct ListNode*)malloc(sizeof(struct ListNode));
	Node->next = NULL;
	Node->prev = NULL;
	Node->data = x;
	return Node;
}

3.链表初始化ListInit函数

代码如下：

struct ListNode* ListInit()
{
	struct ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

4.链表尾部插入数据ListPushBack函数

代码如下：

void  ListPushBack(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* tail = phead->prev;
	struct ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

5.链表头部插入数据ListPushFront函数

代码如下：

void ListPushFront(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* newnode = BuyListNode(x);
	struct ListNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

6.链表尾部删除数据ListPopBack函数

代码如下：

void ListPopBack(struct ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	struct ListNode* tail = phead->prev;
	struct ListNode* second = tail->prev;
	free(tail);
	tail = NULL;
	second->next = phead;
	phead->prev = second;
}

7.链表头部删除数据ListPopFront函数

代码如下：

void ListPopFront(struct ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	struct ListNode* first = phead->next;
	struct ListNode* firstNext = first->next;
	free(first);
	first = NULL;
	phead->next = firstNext;
	first->prev = phead;
}

8.链表查找数据ListFind函数

代码如下：

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

9.链表插入数据ListInsert函数

代码如下：

void ListInsert(struct ListNode* pos, LTDataType x)
{
	assert(pos);
	struct ListNode* newnode = BuyListNode(x);
	struct ListNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

10.链表删除数据ListEarse函数

代码如下：

void ListEarse(struct ListNode* pos)
{
	assert(pos);
	struct ListNode* prev = pos->prev;
	struct ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

12.链表清空数据ListEmpty函数

代码如下：

int ListEmpty(struct ListNode* phead)
{
	assert(phead);
	return phead->next == phead ? 1 : 0;
}

13.链表求解长度ListSize函数

代码如下：

int ListSize(struct ListNode* phead)
{
	assert(phead);
	int size = 0;
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

14.链表销毁ListDestory函数

代码如下：

void ListDestory(struct ListNode* phead)
{
	assert(phead);
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		struct ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

15.链表打印数据ListPrint函数

代码如下：

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

总结

以上就是今天要讲的内容，本文仅仅简单介绍了双向带头循环链表的使用，带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，我们务必掌握。另外，如果有需要源码的私信我即可。还有，，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。