数据结构之“双向链表”

1. 链表的分类

链表的种类有（2x2x2）种，带头/不带头；单向/双向；循环/不循环。

带头/不带头
在之前学习单链表(不带头单向不循环链表)时，它是不带头的，它的第一个结点是可以变的，比如: 我们还可以将第一个结点删除；头插一个数据，等等
但是带头的链表，它的第一个结点（头结点）存储的不是有效数据，其余结点存储的是有效数据。头结点俗称为“哨兵位”，它只是用来占位子的。

单向/双向
单向：只能通过前一个的next找到下一个结点，不能通过下一个结点找到前一个结点的地址。
双向：通过前一个可找到后一个，通过后一个可找到前一个

循环/不循环

2.双向链表

1.全称是：带头双向循环链表
2.双向链表的结点结构：数据+下一个结点的地址next+上一个结点的地址prev

typedef int DataType;

//双像链表的定义
typedef struct ListNode
{
	DataType val;
	struct ListNode* next;
	struct ListNode* prev;
};

3.双向链表在使用之前就要有头结点(哨兵位)。（初始化创建一个头结点）
记得：双向链表是：带头双向循环链表，要循环！！!那必定next和prev不可能指向空，而是指向它自己

//LTNode.c里的内容

LTNode* LTBuynode(DataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode; //上/下结点地址都是自己，达到循环的目的
	return newnode;
}

void LTInit(LTNode** pphead)
{
	//创建一个头结点
	*pphead = LTBuynode(-1);
}

4.双向链表在插入新结点的时候，不需要判断链表有没有头结点。双向链表一定有头结点（哨兵位）。
5.双向链表为空：只有哨兵位。
6.记得写#include<malloc.h> #include<stdlib.h>

2.2 双向链表的打印

记得注意循环打印链表时，什么时候停止打印

void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next; //pcur等于谁呢？不要写成哨兵位了，要写成第一个有效结点
	while (pcur!=phead)   //双向链表打印到什么时候停止，当pcur==phead时
	{
		printf("%d(%p) ->", pcur->val, pcur);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

3.双向链表的插入/删除

双向链表插入或者删除，传过去的都是一级指针。因为phead是头结点,也就是哨兵位。哨兵位是不能被改变的，所以传一级指针。

3.1双向链表的尾插

3.2双线链表的头插

重点：头插是指将新数据成为第一个有效结点，而不是换掉“哨兵位”。

void LTPushFront(LTNode* phead, DataType x)
{
	assert(phead);
	LTNode* newnode = LTBuynode(x);
	
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next->prev = newnode;
	phead->next = newnode;
}

3.3双向链表的尾删

如果双向链表里，只有一个哨兵位，也是不可以删除的。所以要对链表进行判断，是否为空（空就是：phead->next=phead; phead->prev=phead;)。

判断用bool，记得包含头文件#include<stdbool.h>

bool LTempty(LTNode* phead)
{
	//传进来的哨兵位不能为空
	assert(phead);
	return phead->next == phead;
	//如果相等，则是return true
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTempty(phead));  //若链表不为空，则LTempty(phead)返回的是false，!LTempty(phead)则是true
	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;
	free(del);
	del->val = 0;
	del->next = del->prev = NULL;
}

3.4双线链表的头删

bool LTempty(LTNode* phead)
{
	//传进来的哨兵位不能为空
	assert(phead);
	return phead->next == phead;
	//如果相等，则是return true
}

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(!LTempty(phead));  //若链表不为空，则LTempty(phead)返回的是false，!LTempty(phead)则是true
	LTNode* del = phead->next;
	LTNode* Next = del->next;
	phead->next = Next;
	Next->prev = phead;
	free(del);
	del->val = 0;
	del->next = del->prev = NULL;
}

4. 在pos位置之后插入结点

不需要头结点，只需要pos

LTNode* LTFind(LTNode* phead, DataType x)
{
	assert(phead);
	LTNode* pcur = phead->next; //要让pcur是第一个有效结点
	while (pcur != phead)
	{
		if (pcur->val == x)
			return pcur;
		pcur = pcur->next;
	}
}
void LTInsert(LTNode* pos, DataType x)
{
	assert(pos);
	LTNode* newnode = LTBuynode(x); //插入的数据
	LTNode* Next = pos->next;

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

5. 删除pos指定位置的结点

LTNode* LTFind(LTNode* phead, DataType x)
{
	assert(phead);
	LTNode* pcur = phead->next; //要让pcur是第一个有效结点
	while (pcur != phead)
	{
		if (pcur->val == x)
			return pcur;
		pcur = pcur->next;
	}
}
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos->val = 0;
	pos->prev = pos->next = NULL;
}

6. 双向链表的销毁

循环，将每一个结点都销毁（先保存pcur->next，防止pcur销毁之后，找不到下一个结点）。最后将哨兵位也销毁。

传二级指针

void LTDestroy(LTNode** pphead)
{
	assert(pphead && *pphead);
	LTNode* pcur = (*pphead)->next;
	while (pcur != (*pphead))
	{
		LTNode* Next = pcur->next;
		free(pcur);
		pcur = NULL;
		pcur = Next;
	}
	free(*pphead);
	*pphead = NULL;
}

7.比较