【数据结构/C语言】深入理解双向链表

倔强的石头_

发布于 2024-12-06 18:54:44

31800

代码可运行

文章被收录于专栏：C/C++指南C/C++指南

运行总次数：0

代码可运行

一、双向链表的基本概念

双向链表的简介

双向链表是一种常见的数据结构，与单向链表类似，但它允许我们从两个方向遍历链表：向前和向后。每个节点包含三个部分：一个数据元素和两个指针，一个指向链表中的前一个节点，另一个指向链表中的下一个节点。 一般情况下，我们所说的双向链表指的是带头节点，双向，循环链表，以下若无特殊说明，均代表此含义。

以下是常见的单链表与双链表的图示及区别

双向链表的特点

双向遍历：由于每个节点都包含指向前一个节点和下一个节点的指针，因此我们可以从链表的任何一个节点开始，向前或向后遍历链表。
插入和删除操作：在双向链表中插入或删除节点通常比单向链表更加高效，因为我们可以直接访问要插入或删除节点的前一个和/或后一个节点，从而避免了对链表的遍历。
空间效率：与数组相比，双向链表在内存使用上更加灵活。链表可以在运行时动态地分配和释放内存，而不需要预先分配固定大小的内存块。

双向链表的优缺点

优点

动态分配内存，空间效率高。
插入和删除操作效率高，特别是当知道要操作节点的位置时。
可以从两个方向遍历链表。

缺点

相对于数组，链表在内存使用上可能不够紧凑，因为每个节点都需要额外的空间来存储指针。
访问链表中特定位置的元素需要从头或尾开始遍历链表，这可能导致效率较低（尽管可以使用哈希表等数据结构来优化访问速度）。

二、双向链表的结构

双向链表节点的结构

双向链表中的每个节点通常包含以下部分：

数据元素：可以是任何类型的数据，如整数、浮点数、字符串或对象。
prev 指针：指向前一个节点的指针。
next 指针：指向下一个节点的指针。

typedef int LTDataType;//数据类型重定义，可以是任意数据类型
typedef struct ListNode//双向链表节点结构
{
	LTDataType data;//数据
	struct ListNode* prev;//指向前一个节点的指针
	struct ListNode* next;//指向下一个节点的指针
}LTNode;

双向链表的整体结构

相比单链表只有独立存在的每个节点，双向链表多了哨兵位节点，该节点作为头结点，不存储有效数据，只有指向第一个有效节点的next指针和指向尾节点的prev指针。只要链表存在，哨兵位节点就存在

三、双向链表的实现方法

1.双向链表的初始化

双向链表的初始化也就是创建一个哨兵位节点，所以实现初始化之前需要先封装一个节点申请函数

单独封装的申请节点函数

动态申请节点大小的空间
判空
通过形参接受的数据初始化节点数据部分
next指针和prev指针都指向自身（因为双向链表是循环链表）
返回节点地址

LTNode* NewNode(LTDataType x)//申请节点
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("NewNode\n");
		exit(1);
	}
	newnode->data = x;//根据参数初始化数据
	newnode->next = newnode->prev = newnode;//两个指针初始都指向自身
	return newnode;
}

双向链表初始化

调用申请节点函数创建一个哨兵位节点，作为链表的头结点
返回链表头结点地址

注意： 双向链表因为有哨兵位的存在，链表始终不为空，哨兵位节点不会被改变，所以不再需要传递地址，以及用二级指针接收。这一点区别于单链表实现

LTNode* LTInit()            //链表初始化
{
	LTNode* newnode = NewNode(-1);
	return newnode;
}

2.双向链表的头插

双向链表头插

头插就是将新节点插入到哨兵位节点和第一个有效节点之间
形参接收一个哨兵位地址和要插入的数据
首先对哨兵位地址判空，判断链表结构是否正常
申请新节点，存入要插入的数据
接下来是移动指针
一般情况下应当先调整新节点的指针，因为新节点指针调整不会影响到原链表:
新节点prev指向哨兵位，next指向哨兵位的next所指向节点
然后，调整第一个有效节点的prev指针，不再指向哨兵位而是指向新节点；调整哨兵位next指针，不再指向原来的第一个有效节点，而是指向新节点
新节点插入完成

void LTPushFront(LTNode* phead, LTDataType x)//头插
{
	assert(phead);//判空
	LTNode* newnode = NewNode(x);//申请节点

	newnode->next = phead->next;//改变新节点指针指向
	newnode->prev = phead;

	phead->next->prev = newnode;//改变原链表相关节点指针指向
	phead->next = newnode;

}

3.双向链表的尾插

双向链表尾插

尾插就是将新节点插入到原链表最后一个节点和哨兵位之间
首先对哨兵位地址判空，判断链表结构是否正常
申请新节点，存入要插入的数据
调整指针:
新节点next指向哨兵位节点，prev指向原链表最后一个有效节点（哨兵位prev所指向的节点）
原链表最后一个有效节点的next指向新节点
哨兵位prev指向新节点
新节点尾差完成

void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
	assert(phead);//判空
	LTNode* newnode = NewNode(x);//申请节点

	newnode->next = phead;//改变新节点指针指向
	newnode->prev = phead->prev;

	phead->prev->next = newnode;//改变原链表相关节点指针指向
	phead->prev = newnode;
}

4.双向链表的头删

双向链表头删

头删就是将双向链表第一个有效节点删除
（头删的前提是链表至少存在一个有效节点）
首先创建一个指针del指向要删除的节点（哨兵位节点next指向的节点）
然后将第二个有效节点的prev指针指向哨兵位节点
哨兵位节点的next指针指向第二个有效节点
指针修改完成，此时第二个有效节点成为链表的第一个有效节点，释放del指向的节点
（如果删除之前链表只有一个节点，删除完之后只剩下一个哨兵位节点，两个指针都指向自己）

void LTPopFront(LTNode* phead)		//头删
{
	assert(phead && phead->next != phead);//判空
	LTNode* del = phead->next;//暂时存储要删除的节点

	del->next->prev = phead;//移动指针
	phead->next = del->next;

	free(del);//释放节点空间
	del = NULL;
}

5.双向链表的尾删

双向链表尾删

尾删就是将双向链表的最后一个有效节点删除
（尾删的前提是至少存在一个有效节点）
首先创建一个指针del指向要删除的节点（哨兵位prev指向节点）
然后将倒数第二个节点的next指针指向哨兵位
将哨兵位的prev指针指向倒数第二个节点
指针修改完成，此时倒数第二个节点成为最后一个节点，释放del指向的节点
（如果删除之前链表只有一个节点，删除完之后只剩下一个哨兵位节点，两个指针都指向自己）

void LTPopBack(LTNode* phead)		//尾删
{
	assert(phead && phead->next != phead);//判空
	LTNode* del = phead->prev;//暂时存储要删除的节点

	del->prev->next = phead;//移动指针
	phead->prev = del->prev;

	free(del);//释放节点空间
	del = NULL;
}

6.查找节点

双向链表查找（根据数据查找节点）

首先对哨兵位地址判空，否则可能对空地址解引用
创建一个遍历链表的指针，从第一个有效节点开始，将节点数据与要查找的数据进行比对，如果相同返回节点地址
出循环，说明未找到，返回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;
}

7.在指定位置之前插入节点

双向链表在指定位置之前插入节点：

插入的前提是指定位置存在
申请新节点，存入要插入的数据
调整指针:
临时创建一个指针prev指向指定位置节点的perv指向节点
新节点next指针指向指定位置节点，prev指针指向prev节点
然后再修改原链表指针:
指定位置节点的prev指针指向新节点，prev节点的next指针指向新节点
新节点插入完成

void LTInsert(LTNode* pos, LTDataType x)//在pos位置之前插入数据
{
	assert(pos);//判空
	LTNode* newnode = NewNode(x);//申请新节点

	newnode->next = pos;//改变新节点指针指向
	newnode->prev = pos->prev;

	pos->prev->next = newnode;//改变原链表相关节点指针指向
	pos->prev = newnode;

}

8.删除指定位置节点

双向链表删除指定位置节点

删除指定节点的前提是该节点必须存在
首先创建一个指针del指向要删除的节点
然后将该节点的前一个结点的next指针指向它的后一个节点，后一个节点的prev指针指向他的前一个节点
释放该节点
（如果删除之前链表只有一个节点，删除完之后只剩下一个哨兵位节点，两个指针都指向自己）

void LTErase(LTNode* pos)//删除指定位置节点
{
	assert(pos);//判空
	pos->next->prev = pos->prev;//改变要删除节点的前后节点指针指向
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;

}

9.打印链表数据

双向链表数据打印

首先对地址判空，防止对空地址解引用
创建一个遍历链表的指针，从第一个有效节点打印数据，然后向后移动，直到指针遍历到哨兵位

void LTPrint(LTNode* phead)  //链表数据打印
{
	assert(phead);//判空
	LTNode* pcur = phead->next;//遍历链表的指针

	while (pcur != phead)//打印数据
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

10.双向链表销毁

双向链表的销毁

从第一个有效节点开始，创建指针循环遍历链表:
创建next指针临时保存下一个节点，释放本节点，遍历指针指向next节点
循环至有效节点全部被释放
然后将哨兵位节点释放，指针置空，销毁完成

注意： 为了与其他配套函数的参数保持一致，这里的参数本该用二级指针接收，却用一级指针接收。出函数后，需要手动将哨兵位指针置空

四、C语言实现代码及测试

DouSlist.h 双链表头文件

//DouSlist.h 双链表头文件
#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDataType;//数据类型重定义，可以是任意数据类型
typedef struct ListNode//双向链表节点结构
{
	LTDataType data;//数据
	struct ListNode* prev;//指向前一个节点的指针
	struct ListNode* next;//指向下一个节点的指针
}LTNode;

LTNode* NewNode(LTDataType x);//申请节点
LTNode* LTInit();             //链表初始化

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

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


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

void LTInsert(LTNode* pos, LTDataType x);//在pos位置之后插入数据
void LTErase(LTNode* pos);//删除指定位置节点

void LTPrint(LTNode* phead);  //链表数据打印
void LTDestroy(LTNode* phead);//链表销毁

DouSList.c 双链表源文件

//DouSList.c  双链表源文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"DouSList.h"

LTNode* NewNode(LTDataType x)//申请节点
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("NewNode\n");
		exit(1);
	}
	newnode->data = x;//根据参数初始化数据
	newnode->next = newnode->prev = newnode;//两个指针初始都指向自身
	return newnode;
}
LTNode* LTInit()            //链表初始化
{
	LTNode* newnode = NewNode(-1);
	return newnode;
}
void LTPushFront(LTNode* phead, LTDataType x)//头插
{
	assert(phead);//判空
	LTNode* newnode = NewNode(x);//申请节点

	newnode->next = phead->next;//改变新节点指针指向
	newnode->prev = phead;

	phead->next->prev = newnode;//改变原链表相关节点指针指向
	phead->next = newnode;

}
void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
	assert(phead);//判空
	LTNode* newnode = NewNode(x);//申请节点

	newnode->next = phead;//改变新节点指针指向
	newnode->prev = phead->prev;

	phead->prev->next = newnode;//改变原链表相关节点指针指向
	phead->prev = newnode;
}


void LTPopFront(LTNode* phead)		//头删
{
	assert(phead && phead->next != phead);//判空
	LTNode* del = phead->next;//暂时存储要删除的节点

	del->next->prev = phead;//移动指针
	phead->next = del->next;

	free(del);//释放节点空间
	del = NULL;
}

void LTPopBack(LTNode* phead)		//尾删
{
	assert(phead && phead->next != phead);//判空
	LTNode* del = phead->prev;//暂时存储要删除的节点

	del->prev->next = phead;//移动指针
	phead->prev = del->prev;

	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;
}

void LTInsert(LTNode* pos, LTDataType x)//在pos位置之前插入数据
{
	assert(pos);//判空
	LTNode* newnode = NewNode(x);//申请新节点

	newnode->next = pos;//改变新节点指针指向
	newnode->prev = pos->prev;

	pos->prev->next = newnode;//改变原链表相关节点指针指向
	pos->prev = newnode;

}

void LTErase(LTNode* pos)//删除指定位置节点
{
	assert(pos);//判空
	pos->next->prev = pos->prev;//改变要删除节点的前后节点指针指向
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;

}

void LTPrint(LTNode* phead)  //链表数据打印
{
	assert(phead);//判空
	LTNode* pcur = phead->next;//遍历链表的指针

	while (pcur != phead)//打印数据
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

void LTDestroy(LTNode* phead)//链表销毁
{
	assert(phead);//判空
	LTNode* pcur = phead->next;//遍历链表的指针

	while (pcur != phead)//从第一个有效节点开始，逐个释放节点
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);//释放哨兵位节点
	phead = NULL;

}

test.c 测试文件及测试结果

//test.c   测试文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"DouSList.h"

void test1()
{
	LTNode* plist = LTInit();       //链表初始化
	LTPushFront(plist,1 );//头插
	LTPushFront(plist,2 );//头插
	LTPrint(plist);  //链表数据打印
	LTPushBack(plist, 3);//尾插
	LTPushBack(plist, 4);//尾插
	LTPrint(plist);  //链表数据打印

	LTPopBack(plist);		//尾删
	LTPopFront(plist);		//头删
	LTPrint(plist);  //链表数据打印

	LTNode* pos=LTFind(plist, 3);//查找
	LTInsert(pos, 5);//在pos位置之后插入数据
	LTPrint(plist);  //链表数据打印


	LTErase(pos);//删除指定位置节点
	pos = NULL;

	LTPrint(plist);  //链表数据打印

	LTDestroy(plist);//链表销毁
	plist = NULL;
}
int main()
{
	test1();
	return 0;
}

五、双向链表的应用场景

双向链表在许多场景中都非常有用，包括：

LRU 缓存淘汰策略：在操作系统和数据库等系统中，双向链表经常用于实现最近最少使用（LRU）缓存淘汰策略。当缓存满时，最久未使用的项（即链表尾部的项）将被删除。
双向队列：双向链表也可以用作双向队列（Deque），支持从队列的前端和后端添加和删除元素。
撤销/重做功能：在文本编辑器或图形编辑器中，双向链表可以用于实现撤销和重做功能。每当用户执行一个操作时，该操作可以作为一个节点添加到链表的前端。当用户选择撤销时，可以从链表的前端删除一个节点；当用户选择重做时，可以从链表的已删除节点列表中恢复一个节点。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-19，如有侵权请联系 cloudcommunity@tencent.com 删除

数据

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

【数据结构/C语言】深入理解双向链表

【数据结构/C语言】深入理解双向链表

一、双向链表的基本概念

双向链表的简介

双向链表的特点

双向链表的优缺点

二、双向链表的结构

双向链表节点的结构

双向链表的整体结构

三、双向链表的实现方法

1.双向链表的初始化

2.双向链表的头插

3.双向链表的尾插

4.双向链表的头删

5.双向链表的尾删

6.查找节点

7.在指定位置之前插入节点

8.删除指定位置节点

9.打印链表数据

10.双向链表销毁

四、C语言实现代码及测试

DouSlist.h 双链表头文件

DouSList.c 双链表源文件

test.c 测试文件及测试结果

五、双向链表的应用场景

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

【数据结构/C语言】深入理解 双向链表

【数据结构/C语言】深入理解 双向链表

一、双向链表的基本概念

双向链表的简介

双向链表的特点

双向链表的优缺点

二、双向链表的结构

双向链表节点的结构

双向链表的整体结构

三、双向链表的实现方法

1.双向链表的初始化

2.双向链表的头插

3.双向链表的尾插

4.双向链表的头删

5.双向链表的尾删

6.查找节点

7.在指定位置之前插入节点

8.删除指定位置节点

9.打印链表数据

10.双向链表销毁

四、C语言实现代码及测试

DouSlist.h 双链表头文件

DouSList.c 双链表源文件

test.c 测试文件及测试结果

五、双向链表的应用场景

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

【数据结构/C语言】深入理解双向链表

【数据结构/C语言】深入理解双向链表