数据结构：双向链表

代码汇总见：登录 - Gitee.com

与本文章对照理解更好：

数据结构：顺序表-CSDN博客

相关文章：

数据结构：单链表的应用（力扣算法题）第一章-CSDN博客

数据结构：单链表的应用（力扣算法题）第二章-CSDN博客

数据结构：单链表的应用（力扣算法题）第三章-CSDN博客

1.链表的分类

链表的结构非常多样，组合如以下8种：

链表说明：

1.带头或不带头链表

带头链表的头结点中，不存在任何有效的数据，只是用来占位，又名：哨兵位。

2.单向或双向链表

单向链表只能从第一个结点向后走，而双向结点每个有两个指针。

3.循环或不循环链表

在8种链表结构中，我们实际最常用的还是两种结构：单链表（不带头单向不循环链表）和双向链表（带头双向循环链表）。

2.双向链表

2.1概念与结构

注意：这里的“带头”与之前的“头结点”是两个概念，带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只用于”放哨“。

当双向链表为空时，均指向自己：

双向链表中的结点有三个组成部分：

struct ListNode
{
   int data;
   struct ListNode* next;//指向后一个结点
   struct ListNode* prev;//指向前一个结点
};

2.2实现双向链表

依旧创建三个文件：test.c    List.c   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 LTInit(LTNode** pphead);
//初始化02
LTNode* LTInit();

////销毁链表
//void LTDesTroy(LTNode** pphead);
//销毁链表02
void LTDesTroy(LTNode* phead);

//尾插
void LTPushBack(LTNode* phead, LTDataType x);

//头插
void LTPushFront(LTNode* phead, LTDataType x);

//判空
bool LTEmpty(LTNode* phead);

//打印
void LTPrint(LTNode* phead);

//尾删
void LTPopBack(LTNode* phead);

//头删
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos之后插入结点
void LTInsert(LTNode* pos, LTDataType x);

//在pos之前插入结点
void LTInsertFront(LTNode* pos, LTDataType x);

//删除
void LTErase(LTNode* pos);

2.2.1初始化

代码见下：

//初始化
void LTInit(LTNode** pphead)
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	if (*pphead == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	(*pphead)->data = 0;//哨兵结点
	(*pphead)->next = (*pphead)->prev = *pphead;//指向自己
}

调试代码：

2.2.2尾插

在双向链表中，增删改查都不会改变哨兵位结点，所以使用一级指针。

尾插时先建立一个新节点newnode，先改变它的指向，prev指针指向d3，next指针指向哨兵位，再将头结点的前一结点指向newnode，并改变d3指向至newnode。

若原本就是空指针，其操作与非空操作也一模一样。

代码：

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead  phead->prev  newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

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

调用调试：

2.2.3头插

具体思路与尾插大同小异。

代码见下：

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

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

调用调试：

2.2.4判空

在循环双向链表中，有必要单独封装判空函数。

//判空
bool LTEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;//此时链表为空
}

2.2.5打印

终止条件需要注意，不然会一直循环下去。

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

2.2.6尾删

需要将尾删的结点进行保存，不然会找不到其他结点。

代码如下：

//尾删
void LTPopBack(LTNode* phead)
{
	assert(!LTEmpty);

	LTNode* del = phead->prev;
	del->prev->next = phead;
	phead->prev = del->prev;

	free(del);
	del = NULL;
}

调用调试代码：

2.2.7头删

具体思路与尾删相似。

代码见下：

//头删
void LTPopFront(LTNode* phead)
{
	assert(!LTEmpty(phead));

	LTNode* del = phead->next;
	del->next->prev = phead;
	phead->next = del->next;

	free(del);
	del = NULL;
}

调用调试：

LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);
LTPopFront(plist);
LTPrint(plist);

2.2.8查找

代码见下：

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

调用测试：

LTNode* pos = LTFind(plist, 6);
if (pos)
{
	printf("找到了\n");
}
else {
	printf("未找到\n");
}

2.2.9在pos之后插入结点

代码见下：

//在pos之后插入结点
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->prev = pos;
	newnode->next = pos->next;

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

调用测试：

LTNode* pos = LTFind(plist, 2);
LTInsert(pos, 100);
LTPrint(plist);

2.2.10在pos之前插入结点

代码见下：

//在pos之前插入结点
void LTInsertFront(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//pos->prev newnode pos
	newnode->prev = pos->prev;
	newnode->next = pos;

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

调用测试：

LTNode* pos = LTFind(plist, 2);
LTInsert(pos, 100);
LTPrint(plist);
LTInsertFront(pos, 200);
LTPrint(plist);

2.2.11删除pos位置结点

代码见下：

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

	free(pos);
	pos = NULL;
}

调用调试：

LTNode* pos = LTFind(plist, 2);
LTErase(pos);
LTPrint(plist);

2.2.12销毁链表

先从第一个结点开始删除，而不是头结点。

代码如下：

//销毁链表
void LTDesTroy(LTNode** pphead)
{
	LTNode* cur = (*pphead)->next;
	while (cur != *pphead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//销毁头结点
	free(*pphead);
	*pphead = NULL;
}

2.3优化链表

由于有二级指针和一级指针混合，所以为了接口的一致，可以做以下修改：

初始化：

• 通过函数返回值直接返回新创建的头节点地址。
• 调用时通过赋值接收返回值

//初始化02
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(0);
	return phead;
}

调用调试：

LTNode* plist = LTInit();

销毁链表：

• 能销毁所有节点（包括头节点），但最后 phead = NULL; 只修改了函数内部的形参，外部的头指针变量不会被置为 NULL。
• 这会导致外部头指针变成 “野指针”（指向已被 free 的内存），后续若误操作该指针，会引发未定义行为（如非法访问内存）。

//销毁链表02
void LTDesTroy(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//销毁头结点
	free(phead);
	phead = NULL;
}

调用调试：

LTDesTroy(plist);
plist = NULL;

通过比较，初始化推荐用 “返回一级指针” 的方式，销毁用 “二级指针” 的方式，才能保证代码的安全性和健壮性。

3.顺序表与链表的分析

本章完。