数据结构之双向链表

目录

引言 

链表的分类 

双向链表的结构

双向链表的实现 

定义

创建新节点 

初始化 

打印 

尾插

头插 

判断链表是否为空

尾删 

头删

查找与修改 

指定插入

指定删除 

销毁 

顺序表和双向链表的优缺点分析

源代码 

dlist.h

dlist.c

test.c

引言 

数据结构之路在链表章节，前面介绍过单链表，今天我们来介绍最复杂的链表——双向链表（Double Linked List）

链表的分类 

虽然有这么多的链表的结构，但是我们实际中 最常用 还是 两种结构 ： 单链表 和 双向带头循环链表
1. 无头单向非循环链表 ：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的 子结构 ，如 哈希桶、图的邻接表 等等。另外这种结构在 笔试面试 中出现很多。
2. 带头双向循环链表 ：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势， 实现 反而 简单 了，后面我们代码实现了就知道了。

 前面我们讲的单链表，就是无头单向非循环链表，而现在讲的双向链表，就是带头双向循环链表。

双向链表的结构

注意： 这里的 “带头” 跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表里的头节点，实际为“哨兵位” ，哨兵位节点 不存储任何有效元素 ，只是站在这里“放哨的”
“哨兵位”存在的意义：
遍历循环链表避免死循环

双向链表的实现 

定义

与单链表不同，一个节点里有两个指针，分别指向前节点和后节点，实现双向 

创建新节点 

创建新节点与单链表大致相同，抽离成函数方便创建节点

初始化 

双向链表与单链表很大区别，就是在于初始化，创建哨兵位，而哨兵位不存储有效数据，所有这里存入-1，并让prev和next指针都指向自身

打印 

首先assert断言，因为phead指向哨兵位，一定不为空，其次因为双向循环链表里没有NULL，所有停止条件就看哨兵位，当cur指针的下一个为哨兵位时，就代表走到尾部了

尾插

双向循环结构在空链表插入时，带来了极大的便利。因为prev指针的存在，使得找尾十分方便，不用遍历链表，直接访问哨兵位的上一个节点即可

如果是单链表，是不是还要讨论空链表的特殊情况啊？但是，在双向循环链表中，上述代码就可包含所有情况。因为哨兵位的存在，使得链表一定不为空。

 

同时，因为哨兵位的存在，我们不用传二级指针了，只用对结构体进行操作。怎么样，有没有发现双向链表的巨大优势？ 

运行结果

 

头插 

头插时，要注意的就是要先链接后一个节点，再链接前一个节点

运行结果

判断链表是否为空

删除值得注意的是，不能删除哨兵位，要不然后续都无法对链表进行操作，所以专门写个函数来判断除了哨兵位链表是否为空，再用assert断言返回值  

如果phead和phead->next相等，则为空，返回1，即为真 ；不相等，则不为空，返回0，即为假

尾删 

经历过单链表，双向链表的尾删就显得太简单了。找尾tail直接往phead的上一位，同时创建tailPrev，在释放尾部节点后，双向链接哨兵位


运行结果 

头删

同样，双向链表的头删也很简单。 找头first往phead的下一位，再创建second，在释放头部空间后，双向链接哨兵位

运行结果 

查找与修改 

双向链表的查找，找到返回地址，找不到返回NULL。要注意的是从哨兵位的下一位开始找，因为哨兵位是不存储有效数据的，直到重新找到哨兵位

运行结果 

查找到地址后，就可以对其解引用访问，进行修改

指定插入

 在pos前插入

在双向链表，找到pos的上一个节点的地址prev太简单了 

运行结果 

在这里可以复用指定插入函数，快速实现头插和尾插 

头插 

尾插

指定删除 

创建posPrev和posNext两个指针，释放掉pos的节点空间，再相互链接 

在pos删除 

运行结果 

在这里也可以复用指定删除函数，快速实现头删和尾删  

头删 

尾删

大家有没有发现，因为双向链表存在哨兵位，链表不为空，省去了很多关于空链表和空指针的讨论，一路下来浑身舒畅 

销毁 

双向链表的销毁，值得注意的是最后哨兵位也要释放掉，因为为了保持用一级指针的连贯性，所以我们选择最后手动在外部将链表指针置为NULL，实现半自动（和free函数的逻辑一致） 

运行结果 

这样我们就完成了对双向链表的增删查改等功能的实现 

顺序表和双向链表的优缺点分析

我们看到，双向链表的好处是如此巨大的，那是否就代表前面学的顺序表就很low呢？

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O(1)不支持：O(N)
任意位置插入或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁

源代码 

dlist.h

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

typedef int DLDataType;
typedef struct DListNode
{
	struct DListNode* prev;
	struct DListNode* next;
	DLDataType data;
}DLNode;

//初始化
DLNode* DLInit();
//打印
void DLPrint(DLNode* phead);
//销毁
void DLDestroy(DLNode* phead);

//检测链表是否为空
bool DLEmpty(DLNode* phead);
//尾插
void DLPushBack(DLNode* phead, DLDataType x);
//尾删
void DLPopBack(DLNode* phead);
//头插
void DLPushFront(DLNode* phead, DLDataType x);
//头删
void DLPopFront(DLNode* phead);

//查找
DLNode* DLFind(DLNode* phead, DLDataType x);

//在pos前指定插入
void DLInsert(DLNode* pos, DLDataType x);
//在pos指定删除
void DLErase(DLNode* pos);

dlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"dlist.h"

DLNode* BuyDLNode(DLDataType x)
{
	DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}

DLNode* DLInit()
{
	DLNode* phead = BuyDLNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

void DLPrint(DLNode* phead)
{
	assert(phead);
	DLNode* cur = phead;

	printf("Guard");
	while (cur->next != phead)
	{
		cur = cur->next;
		printf("<==>%d", cur->data);
	}
	printf("\n");
}

bool DLEmpty(DLNode* phead)
{
	assert(phead);
	return phead == phead->next;
}

void DLPushBack(DLNode* phead, DLDataType x)
{
	assert(phead);
	DLInsert(phead, x);

	//DLNode* newnode = BuyDLNode(x);
	//DLNode* tail = phead->prev;
	//
	//tail->next = newnode;
	//newnode->prev = tail;
	//phead->prev = newnode;
	//newnode->next = phead;
}

void DLPopBack(DLNode* phead)
{
	assert(phead);
	assert(!DLEmpty(phead));
	DLErase(phead->prev);

	//DLNode* tail = phead->prev;
	//DLNode* tailPrev = tail->prev;
	//
	//free(tail);
	//tailPrev->next = phead;
	//phead->prev = tailPrev;
}

void DLPushFront(DLNode* phead, DLDataType x)
{
	assert(phead);
	DLInsert(phead->next, x);

	//DLNode* newnode = BuyDLNode(x);
	//DLNode* first = phead->next;

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

void DLPopFront(DLNode* phead)
{
	assert(phead);
	assert(!DLEmpty(phead));
	DLErase(phead->next);

	//DLNode* first = phead->next;
	//DLNode* second = first->next;

	//second->prev = phead;
	//phead->next = second;
	//free(first);
}

DLNode* DLFind(DLNode* phead, DLDataType x)
{
	assert(phead);
	DLNode* cur = phead->next;

	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

void DLInsert(DLNode* pos, DLDataType x)
{
	assert(pos);
	DLNode* newnode = BuyDLNode(x);
	DLNode* prev = pos->prev;

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

void DLErase(DLNode* pos)
{
	assert(pos);
	DLNode* posPrev = pos->prev;
	DLNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

void DLDestroy(DLNode* phead)
{
	assert(phead);
	DLNode* cur = phead->next;

	while (cur != phead)
	{
		DLNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"dlist.h"

TestDList1()
{
	DLNode* plist = DLInit();

	//尾插
	DLPushBack(plist, 1);
	DLPushBack(plist, 2);
	DLPushBack(plist, 3);
	DLPushBack(plist, 4);
	DLPushBack(plist, 5);

	//头插
	DLPushFront(plist, 1);
	DLPushFront(plist, 2);
	DLPushFront(plist, 3);
	DLPushFront(plist, 4);
	DLPushFront(plist, 5);

	//打印
	DLPrint(plist);
}

TestDList2()
{
	DLNode* plist = DLInit();

	//尾插
	DLPushBack(plist, 1);
	DLPushBack(plist, 2);
	DLPushBack(plist, 3);
	DLPushBack(plist, 4);
	DLPushBack(plist, 5);

	//头删
	DLPopFront(plist);
	DLPopFront(plist);
	DLPopFront(plist);

	//打印
	DLPrint(plist);
}

TestDList3()
{
	DLNode* plist = DLInit();

	//头插
	DLPushFront(plist, 1);
	DLPushFront(plist, 2);
	DLPushFront(plist, 3);
	DLPushFront(plist, 4);
	DLPushFront(plist, 5);

	//尾删
	DLPopBack(plist);
	DLPopBack(plist);
	DLPopBack(plist);

	//打印
	DLPrint(plist);
}


TestDList4()
{
	DLNode* plist = DLInit();
	//头插
	DLPushFront(plist, 1);
	DLPushFront(plist, 2);
	DLPushFront(plist, 3);
	DLPushFront(plist, 4);
	DLPushFront(plist, 5);
	//查找与修改
	DLNode* pos = DLFind(plist, 4);
	if (pos != NULL)
	{
		pos->data = 40;
		//在pos前指定插入
		DLInsert(pos, 100);
	}
	//打印
	DLPrint(plist);
}

TestDList5()
{
	DLNode* plist = DLInit();
	//头插
	DLPushFront(plist, 1);
	DLPushFront(plist, 2);
	DLPushFront(plist, 3);
	DLPushFront(plist, 4);
	DLPushFront(plist, 5);
	//查找与修改
	DLNode* pos = DLFind(plist, 4);
	if (pos != NULL)
	{
		pos->data = 40;
		//在pos指定删除
		DLErase(pos);
	}
	//打印
	DLPrint(plist);
}

TestDList6()
{
	DLNode* plist = DLInit();
	//尾插
	DLPushBack(plist, 1);
	DLPushBack(plist, 2);
	//头插
	DLPushFront(plist, 1);
	DLPushFront(plist, 2);
	//打印
	DLPrint(plist);
	//销毁
	DLDestroy(plist);
	plist = NULL;
}

int main()
{
	TestDList6();
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/134460.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LeetCode【923】三数之和的多种可能性

LeetCode【923】三数之和的多种可能性

题目&#xff1a; 思路&#xff1a; https://www.jianshu.com/p/544cbb422300 代码&#xff1a; int threeSumMulti(vector<int>& A, int target) {//Leetcode923:三数之和的多钟可能//initialize some constint kMod 1e9 7;int kMax 100;//calculate frequenc…
阅读更多...
图论12-无向带权图及实现

图论12-无向带权图及实现

文章目录 带权图1.1带权图的实现1.2 完整代码 带权图 1.1带权图的实现 在无向无权图的基础上&#xff0c;增加边的权。 使用TreeMap存储边的权重。 遍历输入文件&#xff0c;创建TreeMap adj存储每个节点。每个输入的adj节点链接新的TreeMap&#xff0c;存储相邻的边和权重 …
阅读更多...
138.随机链表的复制（LeetCode）

138.随机链表的复制（LeetCode）

深拷贝&#xff0c;是指将该链表除了正常单链表的数值和next指针拷贝&#xff0c;再将random指针进行拷贝 想法一 先拷贝出一份链表&#xff0c;再对于每个节点的random指针&#xff0c;在原链表进行遍历&#xff0c;找到random指针的指向&#xff0c;最后完成拷贝链表random…
阅读更多...
Java自学第10课：JavaBean和servlet基础

Java自学第10课：JavaBean和servlet基础

目录 目录 1 JavaBean &#xff08;1&#xff09;概念 &#xff08;2&#xff09;分类 &#xff08;3&#xff09;使用 2 servlet &#xff08;1&#xff09;代码结构 &#xff08;2&#xff09;常用接口 &#xff08;3&#xff09;如何开发 1 新建servlet 2 配置 1…
阅读更多...
19 异步通知

19 异步通知

一、异步通知 1. 异步通知简介 阻塞和非阻塞两种方式都是需要应用程序去主动查询设备的使用情况。 异步通知类似于驱动可以主动报告自己可以访问&#xff0c;应用程序获取信号后会从驱动设备中读取或写入数据。 异步通知最核心的就是信号&#xff1a; #define SIGHUP 1 /* 终…
阅读更多...
C详细的字符串函数

C详细的字符串函数

但行前路&#xff0c;莫问归期 要注意的是&#xff0c;要使用下边所讲的函数要包含头文件<string.h> 文章目录 strlenstrcpystrncpy strcatstrncat strcmpstrncmp strstrstrtokstrerror字符串大小写转换struprstrlwr memcpymemmovememcmp strlen 求字符串的长度 函数参…
阅读更多...
Typescript -尚硅谷

Typescript -尚硅谷

基础 1.ts是以js为基础构建的语言&#xff0c;是一个js的超集(对js进行了扩展)&#xff1b; 2.ts(type)最主要的功能是在js的基础上引入了类型的概念; Js的类型是只针对于值而言&#xff0c;ts的类型是针对于变量而言 Ts可以被编译成任意版本的js&#xff0c;从而进一步解决了…
阅读更多...
MySQL Command Line Client 运行闪退问题解决，缺少my.ini文件

MySQL Command Line Client 运行闪退问题解决，缺少my.ini文件

MySQL Command Line Client 运行闪退问题解决&#xff1a; 问题排查&#xff1a; 1.找到Command Line Client的路径位置&#xff0c;并查看属性&#xff0c;步骤截图&#xff1a; 查看属性&#xff1a; 查看属性中的目标路径&#xff1a; 2.进入属性中的目标路径&#xff0c;…
阅读更多...
基于SSM+Vue的电子商城的设计与实现

基于SSM+Vue的电子商城的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…
阅读更多...
记录--vue3 setup 中国省市区三级联动options最简洁写法，无需任何库

记录--vue3 setup 中国省市区三级联动options最简洁写法，无需任何库

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 在写页面的时候&#xff0c;发现表单里面有一个省市区的 options 组件要写&#xff0c;因为表单很多地方都会用到这个地址选择&#xff0c;我便以为很简单嘛。 虽然很简单的一个功能&#xff0c;但是网…
阅读更多...
C#中的扩展方法---Extension

C#中的扩展方法---Extension

C#中扩展方法是C# 3.0/.NET 3.x 新增特性&#xff0c;能够实现向现有类型中“添加”方法&#xff0c;以下主要介绍C#中扩展方法的声明及使用。 1、扩展方法的声明 扩展方法使能够向现有类型“添加”方法&#xff0c;而无需创建新的派生类型、重新编译或以其他方式修改原始类型…
阅读更多...
安全通信网络（设备和技术注解）

安全通信网络（设备和技术注解）

网络安全等级保护相关标准参考《GB/T 22239-2019 网络安全等级保护基本要求》和《GB/T 28448-2019 网络安全等级保护测评要求》 密码应用安全性相关标准参考《GB/T 39786-2021 信息系统密码应用基本要求》和《GM/T 0115-2021 信息系统密码应用测评要求》 1网络架构 1.1保证网络…
阅读更多...
开发知识点-Python

开发知识点-Python

Python从小白到入土 python渗透测试安全工具开发锦集Python安全工具编程基础第一章 Python在网络安全中的应用第一节 Python黑客领域的现状第二节 我们可以用Python做什么第三节 第一章课程内容总结 第二章 python安全应用编程入门第一节 Python正则表达式第二节 Python Web编程…
阅读更多...
虚幻引擎:如何进行关卡切换?无缝切换?

虚幻引擎:如何进行关卡切换?无缝切换?

一丶非无缝切换 在切换的时候会先断开连接,等创建好后才会链接,造成体验差 蓝图中用到的节点是 Execute Console Command 二丶无缝切换 链接的时候不会断开连接,中间不会出现卡顿,携带数据转换地图 1.需要在gamemode里面开启无缝漫游,开启之后使用上面的切换方式就可以做到无缝…
阅读更多...
VueRequest——管理请求状态库

VueRequest——管理请求状态库

文章目录 前言一、为什么选择 VueRequest&#xff1f;二、使用步骤1.安装2.用例 前言 VueRequest——开发文档 VueReques——GitHub地址 在以往的业务项目中&#xff0c;我们经常会被 loading 状态的管理、请求的节流防抖、接口数据的缓存、分页等重复的功能实现所困扰。每次开…
阅读更多...
选购Ipad以及投入学习生产(玩耍)

选购Ipad以及投入学习生产(玩耍)

图片 from Pinterest Ipad Air 5 趁着2023年暑期教育优惠购入&#xff0c;Ipad Air 5 64G版本&#xff0c;附送Apple pencil 2&#xff0c;加上Apple Care服务&#xff08;2年&#xff09;&#xff0c;花费&#xffe5;4899&#xff1b; 因为我知道苹果的电池几年下来就不行了…
阅读更多...
动态规划（4）---Leetcode.746使用最小花费爬楼梯

动态规划（4）---Leetcode.746使用最小花费爬楼梯

题目 给你一个整数数组 cost &#xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用&#xff0c;即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 思路 建…
阅读更多...
Python之文件与文件夹操作及 pytest 测试习题

Python之文件与文件夹操作及 pytest 测试习题

目录 1、文本文件读写基础。编写程序&#xff0c;在 当前目录下创建一个文本文件 test.txt&#xff0c;并向其中写入字符串 hello world。2、编写一个程序 demo.py&#xff0c;要求运行该程序后&#xff0c;生成 demo_new.py 文件&#xff0c;其中内容与demo.py 一样&#xff0…
阅读更多...
C语言——求 n 以内（不包括 n）同时能被 3 和 7 整除的所有自然数之和的平方根 s，n 从键盘输入。

C语言——求 n 以内（不包括 n）同时能被 3 和 7 整除的所有自然数之和的平方根 s，n 从键盘输入。

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h> #include<math.h> int main() {int i,n;double s0.0;printf("输入任意一个自然数&#xff1a; ");scanf("%d",&n);for(i1;i<n;i) {if(i%30&&i%70){si;}}ssqrt(s);printf(…
阅读更多...
Linux C 目录编程

Linux C 目录编程

目录编程 前言目录编程函数mkdir  创建目录rmdir  删除目录opendir  打开目录readdir  读取目录stat  获取文件信息chdir  跳转目录closedir  关闭目录 判断文件类型的宏遍历指定目录及子目录下所有.c文件示例 前言 相较于文件编程&#xff0c;目录编程也有一套自…
阅读更多...
最新文章

Copyright @ 2022~2023