数据结构初阶：双向链表

序言：本篇博客要介绍双向链表的基本概念，包括如何定义和初始化双向链表，以及如何进行数据的插入，删除和销毁等操作。

1.双向链表

1.1 带头双向循环链表

注意：这里的“带头”跟之间我们提及的“头结点”是两个概念，实际前面的在单链表阶段称呼不严谨，但为了更好地理解所以直接称为单链表的头结点。

带头链表里的头结点，实际上是“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨的”。

1.2 实现双向链表

1.2.1 头文件的包含（List.h）

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


//定义双向链表的结构
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;


void LTPrint(LTNode* phead);

//双向链表的初始化   plist  &plist  
//void LTInit(LTNode** pphead);//传地址：形参的改变影响实参
LTNode* LTInit();
//为了保持接口一致性，建议统一参数，都传一级：手动将实参置为NULL
void LTDesTroy(LTNode* phead);

//尾插
//phead结点不会发生改变，参数传一级
//phead结点发生改变，参数传二级
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);

LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的结点
void LTErase(LTNode* pos);

bool LTEmpty(LTNode* phead);

1.2.2 定义链表的结构

//定义双向链表的结构
typedef int LTDataType;
typedef struct ListNode {
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

这段代码主要是定义双向链表的结构。

1.2.3 尾插

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);
	//newnode phead->prev(尾结点） phead
	newnode->prev = phead->prev;
	newnode->next = phead;

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

链表为空时：

代码逻辑：

这段代码定义了一个向双向链表尾部插入节点的函数 `LTPushBack` ，其逻辑如下：

1. 首先使用 `assert` 函数检查传入的头指针 `phead` 是否有效。
2. 通过 `buyNode(x)` 函数创建一个新节点 `newnode` ，并为其数据域赋值为 `x` 。
3. 将 `newnode` 的前驱指针 `prev` 指向原双向链表的尾结点（即 `phead->prev` ），将其后继指针 `next` 指向头节点 `phead` 。
4. 然后将原尾结点的后继指针指向新节点，即 `phead->prev->next = newnode` 。
5. 最后将头节点的前驱指针指向新节点，即 `phead->prev = newnode` 。

通过以上操作，就将新节点成功插入到了双向链表的尾部。

1.2.4 头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);

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

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

代码逻辑： 

这段代码定义了一个在双向链表头部插入节点的函数 `LTPushFront` ，其逻辑如下：

1. 使用 `assert` 函数检查头指针 `phead` 是否有效。
2. 通过 `buyNode(x)` 函数创建一个新节点 `newnode` ，并为其数据域赋值为 `x` 。
3. 将 `newnode` 的前驱指针 `prev` 指向头节点 `phead` ，将其后继指针 `next` 指向头节点的下一个节点 `phead->next` 。
4. 将头节点的下一个节点的前驱指针指向新节点，即 `phead->next->prev = newnode` 。
5. 最后将头节点的后继指针指向新节点，即 `phead->next = newnode` 。

通过以上操作，新节点就被成功插入到了双向链表的头部。

1.2.5 尾删

bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	//phead del->prev(d2) del(d3)
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

 代码逻辑：

这段代码包含两个部分：

1. `bool LTEmpty(LTNode* phead)` 函数用于判断双向链表是否为空。函数中使用 `assert` 函数检查头指针 `phead` 是否有效。然后通过判断头节点的下一个节点是否为头节点本身来确定链表是否为空，如果 `phead->next == phead` ，则表示链表为空，函数返回 `true` ，否则返回 `false` 。

2. `void LTPopBack(LTNode* phead)` 函数用于删除双向链表的尾节点。函数中首先使用 `assert` 函数检查链表是否为空，如果不为空则进行删除操作。通过 `phead->prev` 找到尾节点 `del` ，然后将尾节点的前驱节点的后继指针指向头节点，即 `del->prev->next = phead` ，将头节点的前驱指针指向尾节点的前驱节点，即 `phead->prev = del->prev` 。最后释放尾节点的内存，并将其指针置为 `NULL` ，以防止出现悬空指针。

1.2.6 头删

//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	//phead del del->next
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

 代码逻辑：

这段代码定义的`LTPopFront`函数用于删除双向链表的头节点，其逻辑如下：

1. 使用`assert`函数检查链表是否为空。若链表不为空，则进行删除操作。
2. 通过`phead->next`找到头节点`del`。
3. 将头节点的下一个节点的前驱指针指向头节点，即`del->next->prev = phead`。
4. 将头节点的后继指针指向头节点的下一个节点，即`phead->next = del->next`。
5. 释放头节点的内存，并将其指针置为`NULL`，以防止出现悬空指针。

1.2.7 查找结点

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;

 代码逻辑：

这段代码定义的`LTFind`函数用于在双向链表中查找值为`x`的节点，其逻辑如下：

1. 使用`assert`函数检查头指针`phead`是否有效。
2. 将指针`pcur`初始化为头节点的下一个节点。
3. 通过一个循环，从链表的第一个有效节点开始，逐个比较节点的值与目标值`x`。只要`pcur`不等于头节点，就继续循环。
4. 如果找到值为`x`的节点，即`pcur->data == x`，则函数返回该节点的指针。
5. 如果循环结束后都没有找到值为`x`的节点，函数返回`NULL`，表示未找到。 

 1.2.8 List.c(源代码)

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

LTNode* buyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;

	return node;
}


LTNode* LTInit()
{
	LTNode* phead = buyNode(-1);
	return phead;
}

void LTDesTroy(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
}


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

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);
	//newnode phead->prev(尾结点） phead
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = buyNode(x);

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

	phead->next->prev = newnode;
	phead->next = newnode;
}
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->prev;
	//phead del->prev(d2) del(d3)
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));
	LTNode* del = phead->next;
	//phead del del->next
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = buyNode(x);
	//pos newnode pos->next
	newnode->prev = pos;
	newnode->next = pos->next;

	pos->next->prev = newnode;
	pos->next = newnode;
}
//删除pos位置的结点
void LTErase(LTNode* pos)
{
	assert(pos);

	//pos->prev  pos  pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}

2.顺序表与链表的分析

 3.总结

以上便是本篇博客有关双向链表的所有内容，大家学到知识·的话，还请多多支持博主。