---

带头双向循环链表介绍

初始化链表

首先，我们还是需要先定义一个结点类型，与单向链表相比，双向链表的结点类型中需要多出一个前驱指针，用于指向前面一个结点，实现双向。

typedef int DLTDataType;
typedef struct ListNode
{
	DLTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}DLTNode;
1
2
3
4
5
6
7

然后我们需要一个初始化函数，对双向链表进行初始化，在初始化的过程中，需要申请一个头结点，头结点的前驱和后继指针都指向自己，使得链表一开始便满足循环。

DLTNode* ListInit()
{
	DLTNode* guard = malloc(sizeof(DLTNode));
	if (guard == NULL)
	{
		perror("malloc fail!\n");
		exit(-1);
	}
	guard->prev = guard;
	guard->next = guard;

	return guard;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

销毁链表

销毁链表，从头结点的后一个结点处开始向后遍历并释放结点，直到遍历到头结点时，停止遍历并将头结点也释放掉。

void ListDestory(DLTNode* phead)
{
	assert(phead);

	DLTNode* cur = phead->next;
	while (cur != phead)
	{
		DLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	//传一级指针没用  传二级可以内部置空头结点
	//phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

打印双向链表

打印双向链表时也是从头结点的后一个结点处开始向后遍历并打印，直到遍历到头结点处时便停止遍历和打印（头结点数据不打印）。

void ListPrint(DLTNode* phead)
{
	DLTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10

查找元素

给定一个值，在链表中寻找与该值相同的结点，若找到了，则返回结点地址；若没有找到，则返回空指针(NULL)。

DLTNode* ListFind(DLTNode* phead, DLTDataType x)
{
	assert(phead);

	DLTNode* cur = phead->next;
	while (cur != phead)
	{
		if (x == cur->data)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

指定位置插入节点

在直到位置插入结点，准确来说，是在指定位置之前插入一个结点。我们只需申请一个新结点插入到指定位置结点和其前一个结点之间即可。

void ListInsert(DLTNode* pos, DLTDataType x)
{
	assert(pos); 

	DLTNode* prev = pos->prev;
	DLTNode* NewNode = BuyListNode(x);

	prev->next = NewNode;
	NewNode->prev = prev;
	NewNode->next = pos;
	pos->prev = NewNode;
}
1
2
3
4
5
6
7
8
9
10
11
12

头插和尾插

任何插入都需要增加一个新节点，因此我们需要封装一个函数接口，返回新开辟节点的地址。

DLTNode* BuyListNode(DLTDataType x)
{
	DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
	if (node == NULL)
	{
		perror("malloc fail!\n");
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

头插，即申请一个新结点，将新结点插入在头结点和头结点的后一个结点之间即可。

void ListPushFront(DLTNode* phead, DLTDataType x)
{
	assert(phead);

	//1.普通方法
	DLTNode* NewNode = BuyListNode(x);
	NewNode->next = phead->next;
	phead->next->prev = NewNode;

	phead->next = NewNode;
	NewNode->prev = phead;

	//2.使用之前的Insert直接插入
	//ListInsert(phead->next, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

尾插，申请一个新结点，将新结点插入到头结点和头结点的前一个结点之间即可。因为链表是循环的，头结点的前驱指针直接指向最后一个结点，所以我们不必遍历链表找尾。

void ListPushBack(DLTNode* phead, DLTDataType x)
{
	assert(phead);

	//1.普通方法
	DLTNode* NewNode = BuyListNode(x);
	DLTNode* tail = phead->prev;

	tail->next = NewNode;
	NewNode->prev = tail;
	NewNode->next = phead;
	phead->prev = NewNode;

	//2.使用之前的Insert直接插入
	//ListInsert(phead, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

指定位置删除节点

删除指定位置结点，释放掉目标结点后，建立该结点前一个结点和后一个结点之间的双向关系即可。

void ListErase(DLTNode* pos)
{
	assert(pos);

	DLTNode* prev = pos->prev;
	DLTNode* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
}
1
2
3
4
5
6
7
8
9
10
11

头删和尾删

头删，即释放头结点的后一个结点，并建立头结点与被删除结点的后一个结点之间的双向关系即可。

void ListPopFront(DLTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	//1.普通方法
	DLTNode* first = phead->next;
	DLTNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;

	//2.使用之前的Erase直接插入
	//ListErase(phead->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

尾删，即释放最后一个结点，并建立头结点和被删除结点的前一个结点之间的双向关系即可。

void ListPopBack(DLTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	//1.普通方法
	DLTNode* tail = phead->prev;
	DLTNode* first = tail->prev;

	first->next = phead;
	phead->prev = first;
	free(tail);
	tail = NULL;

	//2.使用之前的Erase直接插入
	//ListErase(phead->prev);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

链表判空

链表判空，即判断头结点的前驱或是后驱指向的是否是自己即可。

bool ListEmpty(DLTNode* phead)
{
	assert(phead);

	return phead->next == phead;
}
1
2
3
4
5
6

获取链表的元素个数

获取链表中的元素个数，即遍历一遍链表，统计结点的个数（头结点不计入）并返回即可。

size_t ListSize(DLTNode* phead)
{
	assert(phead);
	
	size_t n = 0;
	DLTNode* cur = phead->next;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}

	return n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试