双向链表的实现（详解）

前言

链表的分类： 带头 不带头 单向 双向 循环 不循环
一共有 (2 * 2 * 2) 种链表

带头指的是：带有哨兵位节点
哨兵位（头结点）：可以放随机数据，哨兵位指向的下一个节点就是我们的第一个有效节点，我们指的头节点是哨兵位

单向：指针只能从前向后遍历
双向：指针既可以从前向后遍历又可以从后向前遍历
循环：可以通过尾节点找到头节点，从而达到循环

主要使用的链表是单链表和双向链表
单链表:不带头单向不循环
双向链表：带头双向循环

初始化

ListNode* TLInit()
{
	ListNode* phead = ListByNode(-1);//ListByNode后面会介绍
	//为头节点开辟一个空间，并将头结点指向的值赋值为-1
	return phead;
	//将开辟出的头节点返回我们的主函数，主函数中的头节点就知道我们有一个哨兵位了
}

//初始化
void TLInit(ListNode** pphead)
{
	//给双向链表创建一个哨兵位
	*pphead = ListByNode(-1);
}

初始化有两种写法，第二种写法也是可行的，但是用第一种，可以使得接口一致，都是一级指针，使用者也会更方便的使用，不用去记忆那个要用一级指针还是二级指针

双向链表的结构

//定义双向链表的结构
typedef int DataType;
typedef struct ListNode//双向链表
{
	DataType x;//双向链表中的数据
	struct ListNode* next;//指向后一个节点，后继指针
	struct ListNode* prev;//指向前一个节点，前驱指针
}ListNode;

为双向链表的节点开辟空间

ListNode* ListByNode(DataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//开辟成功
	node->next = node->prev = node;
	//初始化一个哨兵位的下一个节点和前一个节点指向的是自己
	node->x = x;

	return node;
}

头插

//头插
//在第一个有效节点之前插入一个节点
void TLPushFront(ListNode* phead,DataType x)
//用一级指针为了不改变原链表的哨兵位
{
	assert(phead);
	//断言一下是不是空链表
	ListNode* newnode = ListByNode(x);

	ListNode* pcur = phead->next;
	newnode->next = pcur;
	newnode->prev = phead;

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

}

尾插

//尾插
//在头节点之后或者之前插入
//因为在哨兵位前，哨兵位的prev指向尾结点，尾结点的next指向哨兵位
void TLPushBack(ListNode* phead,DataType x)
{
	assert(phead);
	//链表不为空
	ListNode* newnode = ListByNode(x);
	//为尾插的节点开辟空间
	ListNode* pcur = phead->prev; 

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

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

打印链表

//打印链表
void TLPrint(ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->x);
		pcur = pcur->next;
	}
	printf("\n");
}

尾删

//尾删
//注意哨兵位不能被删除，所以理论上至少有一个节点，才能够删除
void TLPopBack(ListNode* phead)
{
	assert(phead&&phead->next!=phead);

	ListNode* pcur = phead->prev;

	ListNode* del = pcur->prev;
	del->next = phead;
	phead->prev = del;

	free(pcur);
	pcur = NULL;

}

头删

//头删
//注意哨兵位不能被删除，所以理论上至少有一个节点，才能够删除
void TLPopFront(ListNode* phead)
{
	assert(phead&&phead->next!=phead);
	//phead不能为空

	ListNode* pcur = phead->next;

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

	free(pcur);
	pcur = NULL;

}

查找

//查找 x 数据的位置并返回
ListNode* SLFind(DataType x,ListNode* phead)
{
	ListNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->x == x)
		{
			return pcur;
			//找到了
		}
		pcur = pcur->next;
	}
	return NULL;
	//找不到了
}

指定位置之后的插入

//指定位置之后的插入
//知道了pos节点，就知道了pos之前的数和之后的数
//指定位置之后的插入和指定位置之前的插入是一样的
void TLInsert(ListNode* pos,DataType x)
{
	assert(pos);
	//插入的pos位置不能为空

	ListNode* newnode = ListByNode(x);
	//为插入的数据开辟空间
    
	ListNode* pcur = pos->next;
	newnode->next = pcur;
	newnode->prev = pos;

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

}

删除pos节点

//删除pos节点
void Erase(ListNode* pos)
{
	assert(pos);
	//理论上pos不能为phead,因为phead不能被删除，它是双向链表
	
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;

}

销毁双向链表

//销毁双向链表
void LTDestroy(ListNode* phead)
{
	assert(phead);
	//phead不为空，才销毁，为空，不用销毁
	//销毁时phead也要释放(销毁)

	ListNode* pcur = phead->next;
	ListNode* next = pcur->next;
	while (pcur != phead)
	{
		next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//出来后pcur指向phead
	free(phead);
	phead = NULL;
}