双向链表超详解——连我奶奶都能学会的复杂链表(带头双向循环)

文章目录

  • 前言
  • 一、双向链表的概念
  • 二、双向链的结构设计
  • 三、双链表的基本功能接口
  • 四、双向链表接口的实现
    • 4.1、创建结点
    • 4.2、初始化链表
    • 4.3、打印链表
    • 4.4、尾插结点
    • 4.5、尾删结点
    • 4.6、头插结点
    • 4.7、头删结点
    • 4.8、在pos结点前面插入
    • 4.9、删除pos位置的结点
    • 4.10、查找链表中的某个元素
    • 4.11、链表的销毁
    • 五、总结 全部代码
    • list.c
    • List.h

在这里插入图片描述

前言

前面学过单向链表，单向链表其实就是单向不带头的非循环链表，它不能随机查找，必须从第一个结点开始一个一个的遍历，查找效率比较低，且只有一个指向下一个结点的指针next，它想找到上一个结点还是比较困难的，所以我们今天学习的双向链表就很好的弥补了它的一些缺点。

一、双向链表的概念

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

如图所示：
在这里插入图片描述

二、双向链的结构设计

在这里插入图片描述

三、双链表的基本功能接口

如下所示：

//初始化
LTNode* LTInit();

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

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

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

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

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

//在pos前插入
void LTInsert(LTNode* pos,LTDateType x);

//删除pos位置的结点
void LTErase(LTNode* pos);

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

四、双向链表接口的实现

在此之前先看看双链表的大致模样，如下图：
在这里插入图片描述

4.1、创建结点

使用malloc函数开辟动态内存空间，在开辟的同时不要忘记检查是否开辟成功，若开辟成功，将新结点的prev和next指针都指向NULL（空），并将X赋值给新结点的数据data，最后返回该结点

LTNode* CreateLNode(LTNode* phead,LTDateType x)
{
	//开辟新结点
	LTNode* newnode=(LTNode*)malloc(sizeof(LTNode));
	//判断malloc是否成功开辟
	if(newnode==NULL)
	{
		printf("malloc fali");
		exit(-1);
	}
	newnode->next=NULL;
	newnode->prev=NULL;
	newnode->val=x;
	//返回新结点
	return newnode;
}

4.2、初始化链表

这里我们使用带哨兵位的链表，因为哨兵位不存储有效空间，所以我们就给个-1，将哨兵位的前驱和后继指向自己，即prev和next指针指向自己，最后返回这个头结点，如图所示：

在这里插入图片描述

LTNode* LTInit()
{
	//创建哨兵位
	LTNode* phead=CreateLNode(-1);
	//哨兵位后继指向自己
	phead->next=phead;
	//哨兵位前驱指向自己
	phead->prev=phead;
	//返回哨兵位结点
	return phead;
}

4.3、打印链表

与单链表的打印不同的是，双链表遍历结束的条件并不是 cur等于空，而是cur==phead，也就是等于头结点，因为尾结点的next指向的是头结点。

在这里插入图片描述
代码：

void LTPrint(LTNode* phead)
{
	//断言
	assert(phead);
	//为了美观而这样写的
	printf("哨兵位<=>");
	LTNode* cur=phead->next;
	while(cur!=phead)
	{
		printf("%d<=>",cur->val);
		//让cur往后走，遍历链表
		cur=cur->next;
	}
	printf("\n");
}

4.4、尾插结点

操作要点：
创建新结点，找到位结点tail，将尾结点的后继next指向新结点，新结点的前驱prev指向尾结点，再将新结点的后继next指向头结点，头结点的前驱prev指向新结点即可，也就是将几个结点链起来。

在这里插入图片描述

void LTPushBack(LTNode* phead,LTDateType x)
{
	assert(phead);
	//
	LTNode* newnodw=CreateLNode(x);
    LTNode* tail=phead->prev;
	newnode->prev=tail;
	tail->next=newnode;
	newnode->next=phead;
	phead->prev=newnode;
}

4.5、尾删结点

依旧是遍历找到尾结点定义为指针tail，再找到尾结点tail的前驱，并将其定义为指针tailprev，把tail指向的结点释放掉，然后只需修改它们之间的指向就行了，把tailprev的后继next指向phead，phead的前驱prev指向tailprev。若链表只有哨兵位phead将不能进行删除操作。

在这里插入图片描述
代码：

void LTPopBack(LTNode* phead)
{
	//断言
	assert(phead);
	LTNode*tail=phead->prev;
	LTNode*tailprev=tail->prev;
	free(tail);
	phead->prev=tailprev;
	tailprev->next=phead;
}

4.6、头插结点

创建新结点，将新结点插到头结点（哨兵位的）后面，而不是前面，搞清楚这里就可以改变几个结点指针的指向了，因为d1是phead的next，所以你可以把d1写成phead->next,改变newnode和d1的指向的时候就可以写成newnode->next=phead->next。
在这里插入图片描述
代码：

void LTPushFront(LTNode* phead,LTDateType x)
{
	//断言
	assert(phead);
	LTNode* newnode=CreateLNode(x);

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

4.7、头删结点

定义两个指针，将哨兵位结点的后面一个，也就是第一个结点定义为first，再将first->next定义为second，把first头结点free释放掉置空，最后改变结点的指向就好了，当你把图画好后的操作就相当简单了。如下图所示：
在这里插入图片描述

代码：

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next!=phead);
	LTNode* first=phead->next;
	LTNode* second=first->next;
	phead->next=second;
	second->prev=phead;
	free(first);
	first=NULL;
}

4.8、在pos结点前面插入

有了前面插入操作的基础，实现此接口的功能岂不是轻而易举？通过pos的位置可以直接找到它的前驱将其定义为posprev，然后再改变posprev、newnode和pos的指向，重新接上结点就行了。
在这里插入图片描述
代码：

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* newnode = CreateLTNode(x);
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

4.9、删除pos位置的结点

还是一样根据pos的位置找到它的前驱和后继，并将其定义为posPrev和posNext，将这两个结点链接起来，把pos指向的结点free释放掉即可。看图会更清晰：
在这里插入图片描述
代码：

void LTErase(LTNode* pos)
{
	assert(pos);
	LTNode* posNext = pos->next;
	LTNode* posPrev = pos->prev;

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

4.10、查找链表中的某个元素

从哨兵位的后一个结点开始遍历链表，当cur等于phead停止循环，若找到该元素返回该元素，没找到返回NULL。

代码：

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	//cur从phead的next开始走
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

4.11、链表的销毁

cur从phead的next开始遍历，依次free释放掉每一个结点。

void LTDestroy(LTNode* phead)
{
	assert(phead);

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

五、总结 全部代码

list.c

#include"List.h"



LTNode* CreateLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->val = x;
	newnode->next = NULL;
	newnode->prev = NULL;

	return newnode;
}

LTNode* LTInit()
{
	LTNode* phead = CreateLTNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void LTPrint(LTNode* phead)
{
	assert(phead);
	printf("哨兵位<=>");

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

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev;
	LTNode* newnode = CreateLTNode(x);

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

void LTPopBack(LTNode* phead)
{
	assert(phead);

	// 空
	assert(phead->next != phead);

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

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

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = CreateLTNode(x);

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

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


void LTPopFront(LTNode* phead)
{
	assert(phead);
	// 空
	assert(phead->next != phead);

	LTNode* first = phead->next;
	LTNode* second = first->next;

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

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

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

// 在pos前面的插入
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* newnode = CreateLTNode(x);

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

// 删除pos位置
void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posNext = pos->next;
	LTNode* posPrev = pos->prev;

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

void LTDestroy(LTNode* phead)
{
	assert(phead);

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

}

List.h

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

typedef int LTDateType;
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDateType val;
}LTNode;

//初始化
LTNode* LTInit();

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

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

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

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

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

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

//在pos前插入
void LTInsert(LTNode* pos,LTDateType x);

//删除pos位置的结点
void LTErase(LTNode* pos);

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

走前给个三连呗~
在这里插入图片描述

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

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

相关文章

spring aop核心原理概念

spring aop核心原理概念

目录 概述aop核心概念解析Target(目标对象)Joinpoint(连接点)Advice(通知/增加)Pointcut(切入点)Aspect(切面)Advisor(通知器)Weaving(织入)Proxy(代理)Introduction(引介) 结束 概述 aop核心概念解析 Target(目标对象) 代理的目标对象 目标对象(Target)的确立&#xff0c;是…
阅读更多...
云计算领域的第三代浪潮！

云计算领域的第三代浪潮！

根据IDC不久前公布的数据&#xff0c;2023年上半年中国公有云服务整体市场规模(IaaS/PaaS/SaaS)为190.1亿美元&#xff0c;阿里云IaaS、PaaS市场份额分别为29.9%和27.9%&#xff0c;都远超第二名&#xff0c;是无可置疑的行业领头羊。 随着人工智能&#xff08;AI&#xff09;…
阅读更多...
面试题：什么是自旋锁？自旋的好处和后果是什么呢？

面试题：什么是自旋锁？自旋的好处和后果是什么呢？

文章目录 什么是自旋自旋和非自旋的获取锁的流程 自旋锁的好处AtomicLong 的实现实现一个可重入的自旋锁示例自旋的缺点适用场景 什么是自旋 “自旋”可以理解为“自我旋转”&#xff0c;这里的“旋转”指“循环”&#xff0c;比如 while 循环或者 for 循环。“自旋”就是自己…
阅读更多...
pwn：[NISACTF 2022]ReorPwn?

pwn：[NISACTF 2022]ReorPwn?

题目 按正常方式走&#xff0c;发现指令被反着输出
阅读更多...
抓住机会：2024年企业生成式AI应用的未来

抓住机会：2024年企业生成式AI应用的未来

在 Menlo Ventures 的AI趋势研究报告中&#xff0c;对美国和欧洲的 450 多名企业高管进行了调查&#xff0c;并与另外十几位高管进行了交谈&#xff0c;以了解当今企业应用AI的状况。尽管大肆宣传&#xff0c;与其他软件类别相比&#xff0c;企业对生成式AI的投资仍然小得惊人。…
阅读更多...
qgis添加arcgis的mapserver

qgis添加arcgis的mapserver

左侧浏览器-ArcGIS地图服务器-右键-新建连接 Folder: / 展开-双击图层即可
阅读更多...
Node.js入门指南（三）

Node.js入门指南（三）

目录 Node.js 模块化 介绍 模块暴露数据 导入模块 导入模块的基本流程 CommonJS 规范 包管理工具 介绍 npm cnpm yarn nvm的使用 我们上一篇文章介绍了Node.js中的http模块&#xff0c;这篇文章主要介绍Node.js的模块化&#xff0c;包管理工具以及nvm的使用。 Node…
阅读更多...
排序算法:归并排序、快速排序、堆排序

排序算法:归并排序、快速排序、堆排序

归并排序 要将一个数组排序&#xff0c;可以先将它分成两半分别排序&#xff0c;然后再将结果合并&#xff08;归并&#xff09;起来。这里的分成的两半&#xff0c;每部分可以使用其他排序算法&#xff0c;也可以仍然使用归并排序&#xff08;递归&#xff09;。 我看《算法》…
阅读更多...
【spring（五）】SpringMvc总结 SSM整合流程

【spring（五）】SpringMvc总结 SSM整合流程

目录 一、SpringMVC简介&#xff1a; 二、SpringMVC快速入门&#xff1a; 三、SpringMVC bean的管理&#xff1a;⭐ ①配置bean ②扫描bean 四、SpringMVC配置类&#xff1a;⭐ 五、SpringMVC 请求与响应 六、SpringMVC REST风格 七、SSM整合 异常处理&#xff1a; 八、…
阅读更多...
【STM32】新建工程

【STM32】新建工程

学习来源&#xff1a;[2-2] 新建工程_哔哩哔哩_bilibili 目前STM32的开发主要有基于寄存器的开发方式、基于标准库也就是库函数的方式和基于HAL库的方式。本学习是基于库函数的方式。&#xff08;各种资料去百度云下载&#xff09; 1 建立工程文件夹 Keil中新建工程&#xf…
阅读更多...
浅谈dll劫持免杀

浅谈dll劫持免杀

文章目录 前置知识dll加载dll寻找DLL劫持-白加黑-导入加载DLL劫持-白加黑-导出编译DLL劫持-白加黑-图片分离hookdll原理win api核心代码注意事项 前置知识 基础技能 c语言基本知识win32 API 知识会在微软官网查询APIPE结构知识 原理 DLL劫持的原理主要就是windows下加载DLL…
阅读更多...
医学检验科LIS系统源码 样本采集、检验、分析

医学检验科LIS系统源码 样本采集、检验、分析

LIS把检验、检疫、放免、细菌微生物及科研使用的各类分析仪器&#xff0c;通过计算机联网&#xff0c;实现各类仪器数据结果的实时自动接收、自动控制及综合分析&#xff1b;系统可与条码设备配套使用&#xff0c;自动生成条码&#xff0c;减少实验室信息传递中人为因素导致的误…
阅读更多...
搭建Linux环境 云服务器指南

搭建Linux环境 云服务器指南

我们要学习Linux的相关知识&#xff0c;必须搭建Linux环境 这里有三种方式&#xff1a; 这篇文章我们介绍一下云服务器的购买 购买云服务器 我们以腾讯云为例, 其他的服务器厂商也是类似 云服务器或轻量级应用服务器都是可以的&#xff0c;我们以轻量级应用服务器为例 1.进入…
阅读更多...
初学vue3与ts：setup与setup()下的数据写法

初学vue3与ts：setup与setup()下的数据写法

把setup写在script里 <template><div><div class"index-title">script setup</div><div class"title">字符串&#xff1a;</div><div class"title-sub">ref版&#xff1a;{{strRef}}</div><…
阅读更多...
量子计算 | 解密著名量子算法Shor算法和Grover算法

量子计算 | 解密著名量子算法Shor算法和Grover算法

专栏集锦&#xff0c;大佬们可以收藏以备不时之需 Spring Cloud实战专栏&#xff1a;https://blog.csdn.net/superdangbo/category_9270827.html Python 实战专栏&#xff1a;https://blog.csdn.net/superdangbo/category_9271194.html Logback 详解专栏&#xff1a;https:/…
阅读更多...
数字化转型如何赋能企业实现数字化增值？

数字化转型如何赋能企业实现数字化增值？

随着科技的不断发展&#xff0c;数字化转型已经成为了企业营销的重要趋势。数字化转型不仅可以提高企业的运营效率&#xff0c;还可以更好地满足消费者的需求&#xff0c;提升企业的市场竞争力。 一、数字化转型可以提高企业营销的精准性 在传统的企业营销中&#xff0c;营销人…
阅读更多...
FreeRTOS学习之路，以STM32F103C8T6为实验MCU（2-5：队列）

FreeRTOS学习之路，以STM32F103C8T6为实验MCU（2-5：队列）

学习之路主要为FreeRTOS操作系统在STM32F103&#xff08;STM32F103C8T6&#xff09;上的运用&#xff0c;采用的是标准库编程的方式&#xff0c;使用的IDE为KEIL5。 注意&#xff01;&#xff01;&#xff01;本学习之路可以通过购买STM32最小系统板以及部分配件的方式进行学习…
阅读更多...
Robust taboo search for the quadratic assignment problem-二次分配问题的鲁棒禁忌搜索

Robust taboo search for the quadratic assignment problem-二次分配问题的鲁棒禁忌搜索

文章目录 摘要关键字结论研究背景1. Introduction 常用基础理论知识2. The quadratic assignment problem3. Taboo search3.1. Moves3.2 Taboo list3.3. Aspiration function3.4. Taboo list size4. Random problems5. Parallel taboo search 研究内容、成果7. Conclusion 潜在…
阅读更多...
Spring AOP：什么是AOP? 为什么要用AOP？如何学习AOP?

Spring AOP：什么是AOP? 为什么要用AOP？如何学习AOP?

文章目录 &#x1f386;前言1.为什么要用 AOP3.如何学习去 AOP?3.1 AOP 的组成切面&#xff08;Aspect&#xff09;连接点&#xff08;Join Point&#xff09;切点&#xff08;Pointcut&#xff09;通知&#xff08;Advice&#xff09; 3. Spring AOP 实现3.1 普通的方式实现 …
阅读更多...
画中画视频剪辑：如何实现多画面融合，提升创作质量

画中画视频剪辑：如何实现多画面融合，提升创作质量

在视频剪辑的过程中&#xff0c;画中画是一种常见的技巧&#xff0c;它能够将多个画面融合在一起&#xff0c;创造出一种独特的效果&#xff0c;增强视频的观赏性和表现力。这种技巧常常用于电影、电视和广告中&#xff0c;以增加视觉冲击力&#xff0c;引导注意力&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023