[数据结构与算法]数据结构（3）——双链表的实现

在数据结构（2）中，我实现了其中一种较为常用的链表形式-单向无头非循环链表。那在这篇博客中，我来实现另一种——双向带头循环链表。

结构示意图:

该链表

1. 包含一个哨兵位的头结点；
2. 每一个结点都有两个指针，分别指向上一个结点的后指针和下一个结点的前指针；
3. 最后一个结点的后指针指向哨兵位头结点的前指针，构成闭环；

双向有头循环链表结构较为复杂，实现起来也需要较多的思维量和代码量，但是在运用时会比单向链表方便很多。这次我们也是分为三个文件：

1. Dlist.h
2. Dlist.c
3. Test.c

一、Dlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;
struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	DataType data;
};

我们要实现的功能函数有：

//1.创建一个新结点
//这是内部函数使用的，不是对外开放的接口函数
struct ListNode* BuyListNode(DataType x);

//2.创建链表+初始化
struct ListNode* ListInit();

//3.打印
void ListPrint(struct ListNode* pHead);

//4.尾插
void PushBack(struct ListNode* pHead, DataType x);

//5.头插
void PushFront(struct ListNode* pHead, DataType x);

//6.尾删
void ListPopBack(struct ListNode* pHead);

//7.头删
void ListPopFront(struct ListNode* pHead);

//8.查找
struct ListNode* ListFind(struct ListNode* pHead,DataType x);

//9.在所选位置的前面插入
void ListInsert(struct ListNode* pos, DataType x);

//10.指定位置删除
void ListErase(struct ListNode* pos);

//11.链表判空
int If_List_IsEmpty(struct ListNode* pHead);

//12.计算链表结点个数
int ListSize(struct ListNode* pHead);

//13.释放整个链表
void ListDestroy(struct ListNode** pHead);

二、Dlist.c
那么，我们来具体实现各个功能函数：

1.创建一个新结点

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

2.创建链表+初始化

struct ListNode* ListInit()
{
	struct ListNode* pHead=BuyListNode(0);
	
	//为了实现循环，先让两个指针都指向自己
	pHead->next = pHead;
	pHead->prev = pHead;
	return pHead;
} 

3.打印

在单链表的遍历打印中，循环终止的条件是找尾。但由于双链表是循环的，没有真正意义上的尾，因此对循环终止条件的思考就尤为重要了。

void ListPrint(struct ListNode* pHead)
{
	struct ListNode* cur = pHead->next;
	//注意循环终止的条件
	//循环从头开始，再次到达头时，循环结束
	while (cur != pHead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
}

4.尾插

示意图：

根据示意图可知，尾插的本质就是四个指针的变化。

void PushBack(struct ListNode* pHead, DataType x)
{
	assert(pHead);

    //根据链表双向的特性，头结点的prev指针指向的就是链表的尾结点
	struct ListNode* tail = pHead->prev;
	struct ListNode* newNode = BuyListNode(x);

	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = pHead;
	pHead->prev = newNode;	
}

5.头插

示意图：

void PushFront(struct ListNode* pHead,DataType x)
{
	assert(pHead);
	struct ListNode* newNode = BuyListNode(x);
	struct ListNode* nextpoint = pHead->next;

	pHead->next=newNode;
	newNode->prev = pHead;
	newNode->next = nextpoint;
	nextpoint->prev = newNode;
}

在单链表的头插中，我们将链表中只有一个结点的情况和大于一个结点的情况分开讨论。但在双链表的头插中，我们发现这段代码同时适用于两种情况。
因为如果插入的是第一个结点，那么pHead->next还是pHead,即nextPoint与pHead相同，最后四句相当于是相同的两句写了两遍。

在编写代码时，一定要充分考虑到可能出现的各种极端情况。

6.尾删

示意图：

void ListPopBack(struct ListNode* pHead)
{
	assert(pHead);
	//如果链表中只有pHead一个结点，下面的free(teil)会把pHead释放掉，这是不行的
	assert(pHead->next!= pHead);

	struct ListNode* tail = pHead->prev;
	struct ListNode* prevtail = tail->prev;
	free(tail);

	prevtail->next = pHead;
	pHead->prev = prevtail;
}

如果链表中除了pHead外只有一个结点，以上代码也是适用的。
因为prevail->tail=pHead就相当于pHead->tail=pHead,pHead->next=pretail就相当于pHead->next=pHead，考虑到双向链表的循环性，这是没有问题的。

7.头删

示意图：

注意：头删不是删除pHead，pHead是哨兵位头结点！而是从pHead后面的结点开始删。

void ListPopFront(struct ListNode* pHead)
{
	assert(pHead);
	assert(pHead->next != pHead);

	struct ListNdoe* first = pHead->next;
	struct ListNode* second = pHead->next->next;

	free(first);
	
	pHead->next = second;
	second->prev = pHead;
}

8.查找

struct ListNode* ListFind(struct ListNode* pHead,DataType x)
{
	assert(pHead);

	struct ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

9.指定位置插入

示意图：

void ListInsert(struct ListNode* pos, DataType x)
{
	assert(pos);

	struct ListNode* newNode = BuyListNode(x);
	struct ListNode* posprev = pos->prev;
	 
	posprev->next = newNode;
	newNode->prev = posprev;
	newNode->next = pos;
	pos->prev = newNode;
}

10.指定位置删除

void ListErase(struct ListNode* pos)
{
	assert(pos);

	struct ListNode* prevpos = pos->prev;
	struct ListNode* nextpos = pos->next;

	prevpos->next = nextpos;
	nextpos->prev = prevpos;

	free(pos);
}

头插尾插、头删尾删都可以由Insert和Erase复用得到。因此如果要快速编写双链表，先写ListInsert和ListErase，再通过复用得到其他的功能函数。

11.链表判空

int If_List_IsEmpty(struct ListNode* pHead)
{
	return pHead->next == NULL ? 1 : 0;
}

12.计算链表结点个数

这个函数类似于打印，遍历时的终止条件也是cur==pHead。

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

13.删除整个链表

void ListDestroy(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;
}

三、Test.c
现在，我们对所写的双链表进行简单的测试：

#include "List.h"

void Testfunc1()
{
	struct ListNode* pHead =ListInit();
	 
	printf("            尾插: ");
	PushBack(pHead, 1);
	PushBack(pHead, 2);
	PushBack(pHead, 3);
	PushBack(pHead, 4);
	ListPrint(pHead);

	printf("            头插: ");
	PushFront(pHead, 0);
	PushFront(pHead, -1);
	PushFront(pHead, -2);
	PushFront(pHead, -3);
	ListPrint(pHead);

	struct ListNode* temp = ListFind(pHead, 3);
	printf("在3的前面插入100: ");
	ListInsert(temp, 100);
	ListPrint(pHead);

	printf("           删除3: ");
	ListErase(temp);
	ListPrint(pHead);


	printf("            尾删: ");
	ListPopBack(pHead);
	ListPopBack(pHead);
	ListPopBack(pHead);
	ListPrint(pHead);

	printf("            头删: ");
	ListPopFront(pHead);
	ListPopFront(pHead);
	ListPopFront(pHead);
	ListPrint(pHead);

	int IsEmpty = If_List_isEmpty(pHead);
	if (IsEmpty == 1)
	{
		printf("空链表\n");
	}
	else
	{
		printf("不是空链表,目前有 %d 个结点\n",ListSize(pHead));
	}

	ListDestroy(pHead);
}

int main()
{
	Testfunc1();
	return 0;

运行结果：