（C语言）双向链表

目录

链表的分类

双向链表的实现

1）定义链表

2）初始化双向链表

3）申请节点

4）尾插

5）头插

6）打印链表

7）尾删

8）头插

9）查找

10）指定位置删除

11）在指定位置后删除

12）销毁链表

链表的分类

根据链表的三个特点（带头/不带头，单向/双向，循环/不循环），可以将链表分为8种。常见的有两种：单链表（单向不带头不循环链表），双链表（双向带头循环链表）。是否带头指的是有没有头节点。链表（全网最详细）-CSDN博客。单链表已经写过了，此处我们将双链表。

双向链表的实现

1）定义链表

typedef int SLDateType;

//定义双向链表
typedef struct ListNode
{
	SLDateType date;   //节点中的邮箱有效数据
	struct ListNode* next;  //保存下一个节点地址
	struct ListNode* prev;   //保存上一个节点的有效地址
}LN;

2）初始化双向链表

双链表的初始化，主要是创建头节点，即哨兵位。

//双链表的初始化
void List_start(LN** head)
{
	*head = (LN*)malloc(sizeof(LN));
	(*head)->date = -1;//给哨兵位一个数据，但是它其实是无效数据
	//注意因为是循环链表，所以当只有一个哨兵位的时候，要让它指向它自己；
	(*head)->next = (*head)->prev = (*head);
}

3）申请节点

//申请节点
LN* ListBuyNode(SLDateType x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	newnode->date = x;
	//因为是双向循环链表，永远不会走到空，所以将新节点也指向其自己
	newnode->next = newnode->prev = newnode;
	return newnode;
}

4）尾插

注意：除了双向链表的初始化以及销毁要传二级指针，其他函数均采用一级指针，因为哨兵位在被定义后就不能再对他进行修改了。

//双向链表的尾插
void SLpushback(LN* head, SLDateType x)
{
	LN* newnode = ListBuyNode(x);
	//对头节点head，尾节点head->prev，新节点newnode
	newnode->next = head;
	newnode->prev = head->prev;

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

5）头插

头插是指查到烧饼位的后面。

//双向链表的头插
void SLpushfront(LN* head, SLDateType x)
{
	LN* newnode = ListBuyNode(x);
	//对head newnode head->next进行修改
	newnode->next = head->next;
	newnode->prev = head;

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

6）打印链表

//打印双向链表
void SLPrint(LN* head)
{
	LN* pcur = head->next;
	while (pcur != head)
	{
		printf("%d ", pcur->date);
		pcur = pcur->next;
	}
}

7）尾删

//双链表尾删
void SLDelback(LN* head)
{
	//对head head->prev head->prev->prev
	LN* del = head->prev;
	head->prev = del->prev;
	del->prev->next = head;

	free(del);
	del = NULL;
}

8）头插

//双链表的头插
void SLDelfront(LN* head)
{
	//对head head->next head->next->next进行调整
	LN* del = head->next;
	head->next = del->next;
	del->next->prev = head;
}

9）查找

找双向链表中查找数据，并返回节点；

//双链表的查找
LN* SLFind(LN* head,SLDateType x)
{
	LN* pcur = head->next;
	while (pcur != head)
	{
		if (pcur->date == x)
			return pcur;

		pcur = pcur->next;
	}
	return NULL;
}

10）指定位置删除

//指定位置删除
void SLDEL(LN* head, LN* pos)
{
	//删除pos节点
	//对pos->prev pos pos->next进行操作
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
	pos = NULL;
}

11）在指定位置后删除

//在指定位置后插入
void LInsert(LN* pos, SLDateType x)
{
	LN* newnode = ListBuyNode(x);
	//对pos  newnode  pos->next
	newnode->next = pos->next;
	newnode->prev = pos;

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

12）销毁链表

//销毁链表
void LDestory(LN** head)
{
	//循环删除节点
	LN* pcur = (*head);
	while (pcur != *head)
	{
		LN* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(*head);
	*head = NULL;
}