数据结构--双向链表（图文）

双向链表的概念

双向链表在每个节点处都维护了两个指针，一个指向前一个节点（称为前驱节点），另一个指向下一个节点（称为后继节点）。这种设计使得在链表中的任何一个位置，都可以快速地向前或向后遍历。
在这里插入图片描述

以下是关于双向链表的一些详细概念：

节点结构：每个节点通常由三部分组成：
- 数据域：存储节点的数据元素。
- 前驱指针：指向前一个节点的指针。
- 后继指针：指向下一个节点的指针。
头节点：双向链表的起始节点，通常包含一个特殊节点，称为头节点或头结点。这个头结点不存储实际的数据，它的主要作用是标识链表的起始位置，并简化链表操作，例如插入和删除。
尾节点：链表中的最后一个节点，其后继指针为空（NULL）。
双向遍历：由于每个节点都有指向前后节点的指针，因此可以在双向链表中从前向后或从后向前遍历。
插入与删除操作：双向链表的插入和删除操作相对简单，只需调整相应节点的指针即可。不需要像数组那样进行大量元素的移动，因此时间效率较高。
循环：头节点的后继指针指向尾节点，尾节点的前驱指针又指回头节点，这样的双向链表形成一个环。
动态内存分配：双向链表的节点通常在运行时动态分配，因此链表的长度不固定，可以根据需要扩展或缩减。
内存占用：与单链表相比，双向链表由于每个节点需要额外维护一个前驱指针，因此会占用更多的内存空间。

双向链表相较于单链表的优势在于可以快速访问和操作节点的相邻元素，尤其在需要频繁插入或删除元素的场景中，它提供了更高效的数据操作方式。双向链表常用于实现高级数据结构，如栈、队列、列表等，并且在某些编程语言的标准库中，如C++的STL和Java的LinkedList，都提供了双向链表的实现。

双向链表的实现

首先创建三个文件：

List.h —— 用于声明函数的头文件。
List.c —— 双向链表主要函数的实现。
test.c——测试双向链表。

创建节点

typedef int LTDataType;//方便后续使用更改类型
 
typedef struct ListNode
{
	struct ListNode* next; //指针保存下⼀个节点的地址
	struct ListNode* prev; //指针保存前⼀个节点的地址
	LTDataType data;
}LTNode;

增加一个节点

//增加节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

初始化

为了保持后续接口一致性，我们选择不传参数。

LTNode* LTInit()
{
	LTNode* pplist = LTBuyNode(-1);//创建一个头节点
	return pplist;//返回链表头节点
}

打印函数

遍历打印（不打印头节点）

//打印数据
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 = LTBuyNode(x);
	if (phead->next = phead)//链表只有头节点
	{
	   //先安排新节点
		newnode->next = phead;
		newnode->prev = phead;
		//安排头节点
		phead->next = newnode;
		phead->prev = newnode;
	}
	else
	{
	    //安排新节点
		newnode->next = phead;
		newnode->prev = phead->prev;
		//头节点：phead  尾节点：phead->prev  新节点：newnode
		phead->prev->next = newnode;
		phead->prev = newnode;
	}	
}

尾删数据

情况一：链表只有一个有效节点。

在这里插入图片描述

情况二：链表有多个节点。

代码并没有单独添加情况一的代码，但是将情况一带入后是可以正常尾删的，所以只写情况二的代码即可。

//尾删数据
void LTPopBack(LTNode* phead)
{

	assert(phead&&phead->next!=phead);
	LTNode* freenode = phead->prev;
	phead->prev->prev->next = phead;
	phead->prev = phead->prev->prev;
	free(freenode);
	freenode = NULL;
}

头插数据

情况一：链表只有头节点。
情况二：链表有多个节点。

和上面一样，代码并没有单独添加情况一的代码，但是将情况一带入后是可以正常头插的，所以只写情况二的代码即可。

//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	//下面代码顺序不能换
	phead->next->prev = newnode;
	phead->next = newnode;
}

头删数据

情况一：链表只有一个有效节点。
该情况的代码也可以省略，所以不过多赘述。
情况二：链表有多个节点。

//头删数据
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不为空并且链表的有效数据不能为空
	LTNode* freenode = phead->next;
	phead->next->next->prev = phead;
	phead->next = phead->next->next;
	free(freenode);
	freenode = NULL;
}

指定位置后插入数据

情况一：pos是哨兵位：
情况二：pos是中间位置：
情况三：pos是尾节点：

以下代码在每一种情况下都适用。

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

指定位置删除数据

情况一：pos在中间位置：

在这里插入图片描述

情况二：pos在结尾位置：

以下代码在每一种情况下都适用。

//在pos位置删除数据
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

在双链表中查找指定位置

直接遍历整个双链表，如果没找到就返回NULL，找到就返回该节点。

//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表不能只有哨兵位
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

双向链表源码

List.h

#pragma once

#include 
#include 
#include 

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next; //指针保存下一个节点的地址
	struct ListNode* prev; //指针保存前一个节点的地址
	LTDataType data;
}LTNode;

//初始化
LTNode* LTInit();

//销毁链表
void LTDestroy(LTNode* phead);

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

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

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

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

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

//在pos位置之后插?数据
void LTInsert(LTNode* pos, LTDataType x);

//在pos位置删除数据
void LTErase(LTNode* pos);

//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x);

List.c

#include "List.h"
//增加节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->next = newnode;
	newnode->prev = newnode;
	newnode->data = x;
	return newnode;
}

//初始化
LTNode* LTInit()
{
	LTNode* pplist = LTBuyNode(-1);
	return pplist;
}

//销毁链表
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 = LTBuyNode(x);
	if (phead->next == phead)
	{
		newnode->next = phead;
		newnode->prev = phead;
		phead->next = newnode;
		phead->prev = newnode;
	}
	else
	{
		newnode->next = phead;
		newnode->prev = phead->prev;
		phead->prev->next = newnode;
		//头节点：phead  尾节点：phead->prev   新节点：newnode
		phead->prev = newnode;
	}	
}

//尾删数据
void LTPopBack(LTNode* phead)
{

	assert(phead&&phead->next!=phead);
	LTNode* freenode = phead->prev;
	phead->prev->prev->next = phead;
	phead->prev = phead->prev->prev;
	free(freenode);
	freenode = NULL;
}

//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	//下面代码顺序不能换
	phead->next->prev = newnode;
	phead->next = newnode;

}

//头删数据
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);//链表不为空并且链表的有效数据不能为空
	LTNode* freenode = phead->next;
	phead->next->next->prev = phead;
	phead->next = phead->next->next;
	free(freenode);
	freenode = NULL;
}

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

//在pos位置删除数据
void LTErase(LTNode* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead && phead->next != phead);//链表不能为空并且链表不能只有哨兵位
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

相关阅读:
内网穿透的应用-Cloudreve搭建云盘系统，并实现随时访问
 node的md5加密方式
 python | xlsxwriter，一个实用的 Python 库！
DMSP/OLS夜间灯光数据
 思腾云计算
 Onnxruntime之tensorrt加速
 JavaScript基础(6)_流程控制语句
 微信小程序获取微信用户步数
 element-ui框架的el-dialog弹出框被遮罩层挡住了/el-drawer....会生成v-model元素的组件被遮罩层挡住
 【色彩管理】ICC曲线制作教程
原文地址：https://blog.csdn.net/SouTY_C/article/details/139965556