数据结构第五讲：双链表

1.链表的分类

链表的种类有很多，一下情形结合起来就有八种情况(222)：

1.1带头和不带头链表

带头的链表中的第一个结点为头节点，头节点中不存储有效的数据。
不带头的链表中没有头节点，链表中的第一个结点就开始存储有效的数据。

1.2单向和双向

单向链表是指相邻两个结点之间只通过一条链子进行链接，也就是指结点中只会存储指向下一个结点的指针。
而双向链表相邻两个结点之间是通过两条链子进行链接的，结点中除了存储了一个指向下一个结点的指针外，还存储了一个指向前一个结点的指针。

1.3循环和不循环

循环链表，顾名思义，就是指最后一个结点的next指针不指向NULL，而是指向链表中的某一个结点。
而不循环链表的最后一个结点的next指针指向NULL。

所以对于我们之前了解的单链表来说，它其实是一个不带头单向不循环链表
但是接下来我们要实现的双链表则是一个带头双向循环链表

2.双链表的实现

双链表的基础结构如下：

2.1结点的结构

因为双链表是双向的，所以要有一个指针变量指向下一个结点，一个指针变量指向前一个结点

//结点结构
typedef int ListDataType;

typedef struct ListNode
{
	ListDataType data;//保存数据
	struct LisNode* next;//保存下一个结点的地址
	struct LisNode* prev;//保存上一个结点的地址
}LSTNode;

2.2双链表的初始化

双链表的带头链表，所以初始化时创建一个头节点即可，插入数据直接插入到头节点后即可

//结点的创建
LSTNode* ListBuyNode(ListDataType x)
{
	LSTNode* newnode = (LSTNode*)malloc(sizeof(LSTNode));
	if (newnode == NULL)
	{
		perror("malloc faile!");
		return -1;
	}
	newnode->data = x;
	//因为双链表为循环链表，所以它的头节点的下一个以及上一个指针都要指向自己
	newnode->next = newnode;
	newnode->prev = newnode;
	
	return newnode;
}

//双链表的初始化
void Init(LSTNode** pphead)
{
	//因为双链表是一个带头链表，所以初始化创建一个头节点就可以了
	*pphead = ListBuyNode(-1);
}

2.3双链表的打印

打印需要循环，循环方法看下面代码即可：

//双链表的打印
void ListPrint(LSTNode* phead)
{
	//没有结点不能够打印,并且头节点为空不打印
	assert(phead);

	LSTNode* pcur = phead->next;
	while (pcur != phead)
	{	
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.4双链表的尾插

此时只需要创建一个新的结点，然后将结点与最后一个结点连接起来，改变头节点指针指向的位置即可：

//双链表的尾插
void ListPushBack(LSTNode* phead, ListDataType x)
{
	//如果没有头节点的话不能够尾插
	assert(phead);
	//先创建一块空间
	LSTNode* newnode = ListBuyNode(x);
	//进行插入
	//因为改变创建之后的结点的指针不会影响链表中结点指针的指向，所以首先要对创建过的结点的指针进行初始化
	//1.先找到尾节点存在的位置(尾节点的prev就是尾节点)
	LSTNode* pcur = phead->prev;

	//2.对新建的结点进行赋值
	newnode->next = phead;
	newnode->prev = pcur;

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

2.5双链表的头插

与单链表不同，双链表的头部为头节点之后的那个结点，此时只需要改变指针指向即可：

//双链表的头插
void ListPushFront(LSTNode* phead, ListDataType x)
{
	//头节点为空不能插，只有头节点不能插
	assert(phead && phead->next != phead);

	//这次不仅要找到头节点的位置，还要找到下一个结点的位置
	//1.创建一个结点
	LSTNode* newnode = ListBuyNode(x);
	//2.对新结点进行赋值
	//此时要先存储后一个结点的地址
	LSTNode* pcur = phead->next;
	newnode->next = pcur;
	newnode->prev = phead;

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

2.6双链表的尾删

//双链表尾删
void ListPopBack(LSTNode* phead)
{
	//没有头节点不能删除，没有数据不能删除
	assert(phead && phead->next != phead);

	//1.首先要找到尾节点的位置
	LSTNode* del = phead->prev;

	//先保存末尾位置之前的结点
	LSTNode* left = del->prev;
	//2.进行赋值操作
	phead->prev = left;
	left->next = phead;
	
	//3.释放操作
	free(del);
	del = NULL;
}

2.7双链表的头删

//双链表的头删
void ListPopFront(LSTNode* phead)
{
	assert(phead && phead->next != phead);

	//1.将需要删除的结点和后面的一个结点保存起来
	LSTNode* del = phead->next;
	LSTNode* pcur = del->next;
	//2.改变指针的指向
	phead->next = pcur;
	pcur->prev = phead;
	//3.释放空间
	free(del);
	del = NULL;
}

2.8双链表的查找

//双链表的查找
LSTNode* ListFind(LSTNode* phead, ListDataType x)
{
	assert(phead && phead->next != phead);

	//查找功能直接遍历链表然后进行对照即可
	LSTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

2.9双链表在pos位置之后插入数据

//双链表在pos位置之后插入数据
void ListInsert(LSTNode* pos, ListDataType x)
{
	//pos不能为空
	assert(pos);

	//1.创建一个结点
	LSTNode* newnode = ListBuyNode(x);
	//2.对新节点的指针进行赋值
	LSTNode* next = pos->next;
	//pos newnode next
	newnode->next = next;
	newnode->prev = pos;

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

2.10双链表删除pos位置的结点

//双链表删除pos位置的结点
void ListErase(LSTNode* pos)
{
	assert(pos);

	//1.更改指针的指向
	LSTNode* prev = pos->prev;
	LSTNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	//释放空间
	free(pos);
	pos = NULL;
}

2.11销毁双链表

//销毁双链表
void ListDestroy(LSTNode** pphead)
{
	assert(pphead && *pphead);

	
	LSTNode* prev = (*pphead)->next;
	LSTNode* next = prev->next;
	while (prev != *pphead)
	{
		free(prev);
		prev = next;
		if(next != *pphead)
			next = next->next;
	}
	free(*pphead);
	*pphead =  NULL;
}

3.顺序表与双链表的分析