初阶数据结构之双向链表详解

目录

一：双向链表的概念

1.什么是双向链表？

2.双向链表的优点

3.双向链表的结构

二：双向链表的实现

1.定义链表结点

2.初始化双向链表

3.添加结点

4.尾插

5.头插

6.打印双向链表

7.查找链表结点

8.在指定结点后插入新结点

9.删除指定链表结点

10.头删

11.尾删

12.销毁双向链表

三：代码综合

1.List.h:

2.List.c

3.test.c

开门见山，直接开始讲解。

如果内容对你有所帮助，不妨点个赞再走。（如果有错误请指出，一定改正）

                     

一：双向链表的概念

1.什么是双向链表？

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表，因此，本节的双向链表也是双向循环链表。

2.双向链表的优点

1、双向性：双链表支持在每个节点上存储前驱节点和后继节点的指针，使得在任何节点上都可以方便地找到其前驱节点和后继节点。而单链表只能通过遍历整个链表来查找特定节点的下一个节点或上一个节点，效率较低。

2、插入和删除操作更高效：由于双链表支持双向链接，因此在插入和删除操作中，双链表只需要重新调整相关的指针即可，而不需要像单链表那样需要遍历整个链表。这使得双链表的插入和删除操作更高效。

3、内存利用率更高：双向链表每个节点存储了前驱节点和后继节点的指针，因此可以更充分地利用内存空间。相比之下，单链表每个节点只存储了一个指向下一个节点的指针，内存利用率相对较低。

3.双向链表的结构

图示：

头结点head的prev的指针指向d3，d3的next指针指向head。

同时，无头单向非循环链表和带头双向循环链表也是我们平时最常用的链表结构。

接下来，我们来聊聊双向链表的实现

二：双向链表的实现

在进行链表的实现时，我们把函数的声明放在List.h中，在List.c中实现，在test.c中调用。

1.定义链表结点

在List.h中定义链表结点，data的类型设为DataType,方便以后使用其他类型的数据。

typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* prev;
	struct ListNode* next;

}ListNode;

2.初始化双向链表

初始化链表就是为链表设置一个头结点，头结点内不存储有效数据，只在链表中充当哨兵位的作用，然后把头结点的的prev指针和next指针都指向自己。

传递二级指针的原因是需要把头结点指针的指向改为指向新开辟空间的地址，因为是对地址进行操作，因此要传递二级指针。

//双向链表初始化
void InitList(ListNode** head)
{
	*head = (ListNode*)malloc(sizeof(ListNode));
	if (*head == NULL)
	{
		perror("malloc");
		exit(1);
	}
	(*head)->data = 1;
	(*head)->prev = *head;
	(*head)->next = *head;
}

 运行结果：

3.添加结点

添加链表结点添加链表结点其实就是把非结点结构的数据转换为结点类型的数据，在链表插入新节点时使用。

//添加结点
ListNode* BuyNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = newnode;
	newnode->next = newnode;
	return newnode;
}

4.尾插

代码展示：

//尾插
void PushBack(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head;
	newnode->prev = head->prev;
	head->prev->next = newnode;
	head->prev = newnode;
}

当传过来的x为2时，运行结果：

5.头插

代码展示：

//头插
void PushFront(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev = newnode;
	head->next = newnode;

}

6.打印双向链表

代码展示：

//打印双向链表
void PrintList(ListNode* head)
{
	assert(head && head->next);//判断链表的哨兵位和下一个结点是否为空
	ListNode* tail = head->next;
	while (tail != head)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("\n");
}

 在上面我们已经进行过尾插和头插的操作，让我们打印出来此时链表中的内容为：

7.查找链表结点

//查找结点
ListNode* FindNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* tail = head->next;
	while (tail != head)
	{
		if (tail->data == x)
		{
			return tail;
		}
		tail = tail->next;
	}
}

8.在指定结点后插入新结点

需要先使用FindNode函数查找指定结点，再把x转换为链表类型，最后插入。

//在指定结点后面插入结点
void InsertNode(ListNode* head, DataType a, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,a);
	ListNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

假设a为3，x为6时，运行结果为：

9.删除指定链表结点

删除链表结点要先用FindNode查找结点的地址,然后再进行删除。

//删除指定结点
void DelNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,x);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

假设删除的数据x为3，则运行结果为：

事实证明，我们删除成功了。

10.头删

代码展示：

//头删
void DelFront(ListNode* head)
{
	assert(head && head->next);
	ListNode* first = head->next;
	first->next->prev = head;
	head->next = first->next;
	free(first);
	first = NULL;
}

运行结果：

 头删成功。

11.尾删

//尾删
void DelBack(ListNode* head)
{
	assert(head && head->next);
	ListNode* back = head->prev;
	back->prev->next = head;
	head->prev = back->prev;
}

运行结果：

此时我们的链表中已经没有任何数据了。

12.销毁双向链表

销毁双向链表我们也要传递二级指针，因为在函数操作中也会改变头结点的地址。

//销毁双向链表
void DelList(ListNode** head)
{
	assert(head && *head);
	ListNode* phead = (*head)->next;
	while (phead!=*head)
	{
		ListNode* next = phead->next;创建next指针用来存储下一个结点的地址
		free(phead);
		phead = next;
	}
    free(*head);
	*head=NULL;
}

至此，双向链表的实现全部完成。

三：代码综合

1.List.h:

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

typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* prev;
	struct ListNode* next;

}ListNode;

//双向链表初始化
void InitList(ListNode** head);

//添加结点
ListNode* BuyNode(DataType x);

//尾插结点
void PushBack(ListNode*head,DataType x);

//头插结点
void PushFront(ListNode* head, DataType x);

//打印双向链表
void PrintList(ListNode* head);

//查找结点
ListNode* FindNode(ListNode* head, DataType x);

//指定结点后面插入结点
void InsertNode(ListNode* head,DataType a, DataType x);

//删除指定结点
void DelNode(ListNode* head, DataType);

//头删
void DelFront(ListNode* head);

//尾删
void DelBack(ListNode* head);

//销毁双向链表
void DelList(ListNode** head);

2.List.c

#include"List.h"

//双向链表初始化
void InitList(ListNode** head)
{
	*head = (ListNode*)malloc(sizeof(ListNode));
	if (*head == NULL)
	{
		perror("malloc");
		exit(1);
	}
	(*head)->data = 1;
	(*head)->prev = *head;
	(*head)->next = *head;
}

//添加结点
ListNode* BuyNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = newnode;
	newnode->next = newnode;
	return newnode;
}

//尾插
void PushBack(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head;
	newnode->prev = head->prev;
	head->prev->next = newnode;
	head->prev = newnode;

}

//头插
void PushFront(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev = newnode;
	head->next = newnode;

}

//打印双向链表
void PrintList(ListNode* head)
{
	assert(head && head->next);
	ListNode* tail = head->next;
	while (tail != head)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("\n");
}

//查找结点
ListNode* FindNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* tail = head->next;
	while (tail != head)
	{
		if (tail->data == x)
		{
			return tail;
		}
		tail = tail->next;
	}
}

//在指定结点后面插入结点
void InsertNode(ListNode* head, DataType a, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,a);
	ListNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

//删除指定结点
void DelNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,x);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

//头删
void DelFront(ListNode* head)
{
	assert(head && head->next);
	ListNode* first = head->next;
	first->next->prev = head;
	head->next = first->next;
	free(first);
	first = NULL;
}

//尾删
void DelBack(ListNode* head)
{
	assert(head && head->next);
	ListNode* back = head->prev;
	back->prev->next = head;
	head->prev = back->prev;
}

//销毁双向链表
void DelList(ListNode** head)
{
	assert(head && *head);
	ListNode* phead = (*head)->next;
	while (phead!=*head)
	{
		ListNode* next = phead->next;
		free(phead);
		phead = next;
	}
	free(*head);
	*head =NULL;
}

3.test.c

#include"List.h"
int main()
{
	ListNode* head=NULL;
	//初始化
	InitList(&head);

	//尾插
	PushBack(head, 2);
	printf("%d", head->next->data);

	//头插
	PushFront(head, 3);
	printf("%d\n", head->next->data);

	//打印链表
	PrintList(head);

	//查找结点
	ListNode* node = FindNode(head, 3);

	//指定结点后面插入新节点
	InsertNode(head, 3, 6);
	PrintList(head);

	//删除指定结点
	DelNode(head, 3);
	PrintList(head);

	//头删
	DelFront(head);
	PrintList(head);

	//尾删
	DelBack(head);
	PrintList(head);

	//销毁双向链表
	DelList(&head);
	PrintList(head);

}

完结撒花。

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

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

相关文章

力扣：92. 反转链表 II（Java）

力扣：92. 反转链表 II（Java）

目录 题目描述&#xff1a;示例 1&#xff1a;示例 2&#xff1a;代码实现&#xff1a; 题目描述&#xff1a; 给你单链表的头指针 head 和两个整数 left 和 right &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表节点&#xff0c;返回 反转后的…
阅读更多...
TypeScript-搭建编译环境

TypeScript-搭建编译环境

搭建编译环境 TypeScript 编写的代码是无法直接在js引擎( 浏览器 / Nodejs )中运行的&#xff0c;最终还需要经过编译成js代码才可以正常运行 搭建手动编译环境 1️⃣ 全局安装 typescript 包&#xff08;编译引擎&#xff09; -> 注册 tsc 命令 npm i -g typescript 2…
阅读更多...
如何解决vcruntime140.dll丢失问题，详细介绍5种靠谱的解决方法

如何解决vcruntime140.dll丢失问题，详细介绍5种靠谱的解决方法

vcruntime140.dll是Microsoft Visual C Redistributable Package的一部分&#xff0c;它为使用Visual C编译器开发的应用程序提供必要的运行时环境。该DLL文件包含了大量应用程序运行时需要调用的库函数&#xff0c;这些函数是实现C标准库、异常处理机制、RTTI&#xff08;运行…
阅读更多...
2461. 长度为 K 子数组中的最大和（c++）

2461. 长度为 K 子数组中的最大和（c++）

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和&#xff1a; 子数组的长度是 k&#xff0c;且子数组中的所有元素 各不相同 。 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件&#xff0c;返回 0 。 子数…
阅读更多...
2024电工杯数学建模A题Matlab代码+结果表数据教学

2024电工杯数学建模A题Matlab代码+结果表数据教学

2024电工杯A题保姆级分析完整思路代码数据教学 A题题目&#xff1a;园区微电网风光储协调优化配置 以下仅展示部分&#xff0c;完整版看文末的文章 %A_1_1_A % 清除工作区 clear;clc;close all;warning off; %读取参数%正常读取 % P_LOADxlsread(附件1&#xff1a;各园区典…
阅读更多...
如何创建 Gala Games 账户：解决 Cloudflare 验证指南 2024

如何创建 Gala Games 账户：解决 Cloudflare 验证指南 2024

Gala Games 站在数字娱乐新时代的前沿&#xff0c;将区块链技术与游戏相结合&#xff0c;重新定义了所有权和奖励。本文将引导您创建 Gala Games 账户并使用 CapSolver 解决 Cloudflare 验证难题&#xff0c;确保您顺利进入这一创新的生态系统。 什么是 Gala Games&#xff1f…
阅读更多...
debian nginx upsync consul 实现动态负载

debian nginx upsync consul 实现动态负载

1. consul 安装 wget -O- https://apt.releases.hashicorp.com/gpg | sudo gpg --dearmor -o /usr/share/keyrings/hashicorp-archive-keyring.gpg echo "deb [signed-by/usr/share/keyrings/hashicorp-archive-keyring.gpg] https://apt.releases.hashicorp.com $(lsb_r…
阅读更多...
微信小程序使用input标签遇到的问题

微信小程序使用input标签遇到的问题

场景1&#xff1a;多个input标签切换无法聚焦问题 解决方案1&#xff1a; 在网上搜的用官方给的always-embed属性&#xff0c;但是也明确标注了只有ios可用 解决方案2&#xff1a; 使用focus属性&#xff1a;每次点击input标签都重新设置 wxml: <input adjust-position…
阅读更多...
【YOLOv5/v7改进系列】替换激活函数为SiLU、ReLU、LeakyReLU、FReLU、PReLU、Hardswish、Mish、ELU等

【YOLOv5/v7改进系列】替换激活函数为SiLU、ReLU、LeakyReLU、FReLU、PReLU、Hardswish、Mish、ELU等

一、导言 激活函数在目标检测中的作用至关重要&#xff0c;它们主要服务于以下几个关键目的&#xff1a; 引入非线性&#xff1a;神经网络的基本构建块&#xff08;如卷积层、全连接层等&#xff09;本质上是线性变换&#xff0c;而激活函数通过引入非线性&#xff0c;使得网络…
阅读更多...
画图工具之PlantUML插件使用

画图工具之PlantUML插件使用

文章目录 1 PlantUML插件1.1 引言1.2 什么是PlantUML1.3 PlantUML插件1.3.1 IntelliJ IDEA中插件1.3.2 VS Code中插件1.3.3 使用例子 1.4 PlantUML时序图语法1.4.1 声明参与者1.4.2 消息传递1.4.2.1 同步消息1.4.2.2 异步消息1.4.2.3 返回消息1.4.2.4 自调用 1.4.3 生命线&…
阅读更多...
在Windows10中重命名文件和文件夹的6种方法，有你熟悉和不熟悉的

在Windows10中重命名文件和文件夹的6种方法，有你熟悉和不熟悉的

序言 你可以通过多种方式在Windows 10上重命名文件。如果每次你想更改文件名时仍右键单击并选择“重命名”，那么我们有一些技巧可以加快更改速度。 使用文件资源管理器重命名文件和文件夹 Windows 10的文件资源管理器是一个功能强大的工具。你知道吗，有四种不同的方法可以…
阅读更多...
理解大语言模型（二）——从零开始实现GPT-2

理解大语言模型（二）——从零开始实现GPT-2

相关说明 这篇文章的大部分内容参考自我的新书《解构大语言模型&#xff1a;从线性回归到通用人工智能》&#xff0c;欢迎有兴趣的读者多多支持。 本文涉及到的代码链接如下&#xff1a;regression2chatgpt/ch11_llm/char_gpt.ipynb1 本文将讨论如何利用PyTorch从零开始搭建G…
阅读更多...
【Linux网络】端口及UDP

【Linux网络】端口及UDP

文章目录 1.再看四层2.端口号2.1引入linux端口号和进程pid的区别端口号是如何生成的传输层有了pid还设置端口号端口号划分 2.2问题2.3netstat 3.UDP协议3.0每学一个协议 都要讨论一下问题3.1UDP协议3.2谈udp/tcp实际上是在讨论什么&#xff1f; 1.再看四层 2.端口号 端口号(Po…
阅读更多...
MyBatis-Plus介绍及Spring Boot 3集成指南

MyBatis-Plus介绍及Spring Boot 3集成指南

我们每个Java开发者都在使用springbootmybatis开发时&#xff0c;我们经常发现自己需要为每张数据库表单独编写XML文件&#xff0c;并且为每个表都需要编写一套增删改查的方法&#xff0c;较为繁琐。为了解决这一问题&#xff0c;MyBatis-Plus应运而生。在本文中&#xff0c;我…
阅读更多...
【简单介绍下7-Zip，什么是7-Zip？】

【简单介绍下7-Zip，什么是7-Zip？】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…
阅读更多...
顶顶通实时质检系统新增一大功能：黑名单功能介绍

顶顶通实时质检系统新增一大功能：黑名单功能介绍

文章目录 前言联系我们功能介绍配置方案 前言 顶顶通实时质检系统新增黑名单一大功能。该功能可通过调用质检系统的黑名单接口&#xff0c;对被叫号码进行检测。如果被检测的号码符合所设定的拦截规则&#xff0c;就会对当前呼叫进行拦截&#xff0c;取消呼叫。 联系我们 有意…
阅读更多...
网络拓扑—WEB-IIS服务搭建

网络拓扑—WEB-IIS服务搭建

文章目录 WEB-IIS服务搭建网络拓扑配置网络IISPC 安装IIS服务配置IIS服务&#xff08;默认站点&#xff09;PC机访问网页 配置IIS服务&#xff08;新建站点&#xff09;PC机访问网页 WEB-IIS服务搭建 网络拓扑 //交换机忽略不计 IIS服务IP&#xff1a;192.168.1.1 PC机IP&…
阅读更多...
汇编：函数以及函数参数传递

汇编：函数以及函数参数传递

汇编语言中的函数&#xff08;或过程&#xff09;是指一段可以被调用和执行的代码块&#xff1b;它们用于组织和重用代码&#xff0c;并使程序结构更加清晰&#xff1b;由于汇编语言没有高层次语言的语法糖&#xff0c;编写和调用函数涉及直接的堆栈操作和寄存器管理&#xff1…
阅读更多...
基于 N-Gram 文本分类的语言检测器（附详细实现源码）

基于 N-Gram 文本分类的语言检测器（附详细实现源码）

基于 N-Gram 文本分类的语言检测器 文本分类是文档处理的一项基本任务&#xff0c;可以自动处理大量的电子文档流。处理某些类别文档的一个困难是存在不同类型的文本错误&#xff0c;例如电子邮件中的拼写和语法错误&#xff0c;以及通过 OCR 处理的文档中的字符识别错误。文本…
阅读更多...
NebulaGraph

NebulaGraph

文章目录 关于 NebulaGraph客户端支持安装 NebulaGraph关于 nGQLnGQL 可以做什么2500 条 nGQL 示例原生 nGQL 和 openCypher 的关系 Backup&Restore功能 导入导出导入工具导出工具 NebulaGraph ImporterNebulaGraph ExchangeNebulaGraph Spark ConnectorNebulaGraph Flink …
阅读更多...
最新文章

Copyright @ 2022~2023