【数据结构】双向链表(真正的零基础)

链表是一种物理存储单元上非连续非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的!在上篇我们学习了单向链表,而单向链表虽然空间利用率高,插入和删除也只需改变指针就可以达到!但是我们在每次查找、删除、访问.....时,都受到单向链表的一个特性干扰:单向不可逆,只能以遍历的形式去使用,这样使得需要从头到尾找到特定的节点再进行操作!今天我们来学习另外一种链表结构:双向链表。既然是零基础,我会从小白的角度进行讲解!放心食用!

目录

                                                            一.链表的分类

                                                   二.带头双向循环链表

                                                                               二.(1)链表节点设置

                                                                      二.(2)链表新增节点

                                                             二.(3)链表初始化 

                                                    二.(4)链表扩容节点

                                                    二.(5)链表打印

                                                    二.(6)在目标节点前面插入

                                                    二.(7)在目标节点后面插入

                                                    二.(8)链表头删

                                                    二.(9)链表尾删

                                                    二.(10)链表头插

                                                    二.(11)链表尾插

                                                    二.(12)删除中间目标节点

                                                    二.(13)释放双链表

               三.总结

               四.代码合并


一.链表的分类

这里就不介绍哈是链表了,如果对此感到疑惑,可以看我上一篇投稿,咱直接进入分类!

链表主要可以分为以下3大类:

单向链表:

单向链表是链表中最简单的一种,它由一系列节点组成,每个节点包含两个部分:指针域与数据域。指针域用来指向下一个节点的地址,数据域用来存储数据。以下是抽象草图,方便巧记:

双向链表:

 双向链表与单向链表不同,它的每个节点有两个指针(nextprev)跟一个数据域,两个指针分别指向前一个节点和后一个节点。同样,如图巧记:

循环链表:
 循环链表是一种特殊的单链表,它的最后一个节点的指针指向头节点,形成一个“环”,如图:

在进行下面的学习之前,针对链表的各种分类,我们需要理清几个名词:

头指针:

头指针本质上是结构体类型的指针,指向一个节点,这个节点一般是 第一个节点 或者 头节点

头结点:

简单理解为在 第一个节点 前面还有一个节点,这个节点就称为头节点。头节点一般不存储数据

带头:

头指针指向头节点就称为带头节点,如图:

不带头: 

头指针指向第一个节点就称为不带头节点,如图:

针对这几种分类:带头或者不带头、单向或者双向、循环或者非循环 

我们总共可以组合八种链表,我们主要学习 无头双向非循环链表     带头双向循环链表    这两种!

八种链表结构中其中这两种最具代表性,另外六种便自然理解了!上一篇我们已经学完了第一种,今天我们来学习第二种!

注意:双链表一般需要改变四个指针的指向,因此建议大家画图理解!这样就可以轻松操作了!

二.带头双向循环链表

理解了上面几个名词后,我们就能轻易理解哈是带头双向循环链表了!

带头:无非就是第一个节点前还有一个头节点嘛!

双向:节点里面有两个指针,两个指针分别指向一前一后的节点

循环:尾节点的后指针指向头节点,头节点的前指针指向尾节点,达到封闭,形成循环!

二.(1)链表节点设置

不论怎样,我们都需要先创建一个结构体作为接下来各种功能的节点基础, 这个结构体里面有两个指针,一个数据域。这里为了缩短结构体类型,我们用 typedef 重定义以下,需要注意的是typedef重定义的这个结构体里面,结构体指针必须写完整,因为此处还属于声明阶段,后续才可以正常缩写。代码如下:

typedef struct Pointdef
{
	struct Pointdef* next;//指向下一个节点
	struct Pointdef* prev;//指向上一个节点
	int data;//数据域
}Pointdef;
二.(2)链表新增节点

因为我们不管初始化还是各种增添功能,都需要节点,所以我们先完成开辟节点的函数,让这个函数返回指向这个开辟好的节点指针,然后才可以进行初始化操作,代码如下:

//开辟新节点
Pointdef* Newspoint(int x)
{
	Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));

	if (news == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//初始化新节点
	news->next = NULL;
	news->prev = NULL;
	news->data = x;

	return news;
}

我们刚开辟好的节点还没有连接,只是一个结构体大小,因此它的prevnext指针都指向NULLx就是初始化节点的数据域,如下图理解:

二.(3)链表初始化 

上面我们先调用 新增节点 的函数,在外面开辟一个节点作为头节点(如果有问题,可以先看下面的合并代码!),接下来对这个头节点进行初始化,将它作为头节点,此时头节点的nextprev指针都应该指向自己(因为是循环链表,此时只有一个节点)。代码如下:

//链表初始化
void Initialize(Pointdef* head)
{
	head->next = head;
	head->prev = head;
}

二.(4)链表扩容节点

此时我们已经初始化了链表,下面我们给它新增几个节点,调用新增函数,改变节点指针指向,代码如下:

//链表扩容节点
Pointdef* tail = head;
for (int i = 2; i <= 5; i++)
{
	Pointdef* news = Newspoint(i);
	//连接
	tail->next = news;
	news->prev = tail;
	news->next = head;
	head->prev = news;

	tail = tail->next;
}

二.(5)链表打印

与单向链表访问区别不大,只需要注意是这里的链表是循环的,需要控制打印的条件不能是当前指针不能指向头节点,否则就是死循环了,代码如下: 

//链表打印
void Printf(Pointdef* head)
{
	Pointdef* tail = head->next;

	while (tail != head)
	{
		printf("%d <= ", tail->data);
		tail = tail->next;
	}
    printf("NULL\n");
}

二.(6)在目标节点前面插入

我们已经写好了一条双链表,那么我们只需要找到目标节点然后连接四个指针就行了,代码如下:

这里我们假设目标节点是 tail ,新节点 news  新节点前面的节点是 prev

//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{
	
	assert(tail);

	Pointdef* prev = tail->prev;
	Pointdef* news = Newspoint(x);

	prev->next = news;
	news->prev = prev;

	news->next = tail;
	tail->prev = news;
	
}

二.(7)在目标节点后面插入

将找到的目标节点作为参数,然后在函数中改变它的前后四个指针就行,如图:

//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{
	assert(tail);
	//目标节点的下一个节点不能是空,否则就是尾插了
	assert(tail->next);

	Pointdef* news = Newspoint(x);
	Pointdef* next = tail->next;

	tail->next = news;
	news->prev = tail;

	news->next = next;
	next->prev = news;
}


 二.(8)链表头删

头删咱直接将头节点作为参数就行了,再记录第二个节点方便释放,然后用四个指针连接头节点和第二个节点,最后记得释放第一个节点的空间,如图:

//链表头删
void Outomit(Pointdef* head,int x)
{
	assert(head);
	assert(head->next);

	Pointdef* tail = head->next->next;
	Pointdef* next = head->next;

	head->next = tail;
	tail->prev = head;

	free(next);
	next = NULL;
}

二.(9)链表尾删

这个咱就不多说了!就是先记录倒数第二个节点,将它作为尾节点就行了,同样记得释放空间,直接上代码:

//链表尾删
void Tailomit(Pointdef* head, int x)
{
	assert(head);

	Pointdef* prev = head->prev->prev;
	Pointdef* tail = head->prev;
	
	prev->next = head;
	head->prev = prev;

	free(tail);
	tail = NULL;
}

二.(10)链表头插

但凡插入节点的都具有很大的相似之处,无非就是将这个节点插入某处,通过记录附近节点的位置,再把新增节点的左右节点与它进行连接,看代码:

//链表头插
void Headinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->next;
	Pointdef* news = Newspoint(x);

	head->next = news;
	news->prev = head;

	news->next = tail;
	tail->prev = news;
}

二.(11)链表尾插
//链表尾插
void Tailinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->prev;
	Pointdef* news = Newspoint(x);

	tail->next = news;
	news->prev = tail;

	head->prev = news;
	news->next = head;
}

二.(12)删除中间目标节点

删除节点我们肯定要先找到目标节点,我们在链表中可以通过以下两种方式寻找:指针域  数据域,在上面的前后插入中,我们选择的指针查找方式,下面我们进行数据查找方式来删除:

//链表中间节点删除
void Omit(Pointdef* tail)
{
	Pointdef* pc = tail->prev;
	Pointdef* pt = tail->next;

	pc->next = pt;
	pt->prev = pc;

	free(tail);
	tail = NULL;
}

二.(13)释放双链表

咋从第一个节点释放到尾就OK了!注意:链表的空间不是连续的,因此需要一个个销毁!

//双链表销毁
void Undermine(Pointdef* head)
{
	assert(head);

	Pointdef* cur = head->next;
	Pointdef* tail = cur->next;

	while (cur != head)
	{
		tail = cur->next;

		free(cur);
		cur = tail;
	}
    free(head);
    head=NULL;

	printf("释放完毕\n");
}
三.总结

针对以上实现的双链表,其实针对整个链表,都有以下特点:

1:首先我们要有设计好开辟节点的函数,然后知道如何连接这些节点

2:头插、尾插、中间插其实都有很大的共性,只是目标地点稍微差异,这点大家可以画图理解!

3:删除某个节点需要及时释放该空间,避免空间泄漏。需要注意是先连接,再释放

4:针对为何单向链表很多涉及二级指针,而双向链表大多是一级指针?

因为单向链表有很多地方需要改变头指针(单向链表将第一个节点作为头节点)的指向,而双向链表是固定了哨兵节点,因此其它操作其实是针对结构体里面的指针操作的。该知识的原理是:对形参的改变不影响实参,如需改变形参,需要使用二级指针

5:双向链表为哈要从第一个节点开始释放?

双向链表的头节点是链表结构的一部分,不是数据节点,应该先释放数据节点,再释放链表结构

四.代码合并

流程文件(可以使用打印来进行功能的测试!)

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"

int main()
{
	int x = 4;

	//链表新增节点
	Pointdef* head=Newspoint(1);

	//链表初始化
	void Initialize(head);

	//链表扩容节点
	Pointdef* tail = head;
	for (int i = 2; i <= 5; i++)
	{
		Pointdef* news = Newspoint(i);
		//连接
		tail->next = news;
		news->prev = tail;
		news->next = head;
		head->prev = news;

		tail = tail->next;
	}
	
	//链表打印
	Printf_t(head);

	//在目标节点前面插入                      
	tail = (head->next)->next;
	x = 6;
	FrontInsertion(tail, x);

	//在目标节点后面插入                
	OutInsertion(tail, x);

	//                                  测试点
	Printf_t(head);

	//链表头删
	x = 7;
	Outomit(head,x);

	//链表尾删
	x = 8;
	Tailomit(head, x);

	//                                  测试点
	Printf_t(head);

	//链表头插
	x = 1;
	Headinsert(head, x);

	//链表尾插
	x = 9;
	Tailinsert(head, x);

	//                                  测试点
	Printf_t(head);

	//链表中间节点删除
	x = 4;
	tail = head -> next;
	while (tail->data != x)
	{
		tail = tail->next;
	}
	Omit(tail);

	//                                   测试点
	Printf_t(head);

	//双链表销毁
	Undermine(head);

	return 0;
}

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>

typedef struct Pointdef
{
	struct Pointdef* next;//指向下一个节点
	struct Pointdef* prev;//指向上一个节点
	int data;//数据域
}Pointdef;

//链表新增节点
Pointdef* Newspoint(int x);
//链表初始化
void Initialize(Pointdef* head);
//链表打印
void Printf_t(Pointdef* head);
//在目标节点前面插入
void FrontInsertion(Pointdef* tail, int x);
//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x);
//链表头删
void Outomit(Pointdef* head ,int x);
//链表尾删
void Tailomit(Pointdef* head, int x);
//链表头插
void Headinsert(Pointdef* head, int x);
//链表尾插
void Tailinsert(Pointdef* head, int x);
//链表中间节点删除
void Omit(Pointdef* tail);
//双链表销毁
void Undermine(Pointdef* head);

函数执行文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"

//链表新增节点
Pointdef* Newspoint(int x)
{
	Pointdef* news = (Pointdef*)malloc(sizeof(Pointdef));

	if (news == NULL)
	{
		perror("malloc");
		return NULL;
	}
	//初始化新节点
	news->next = NULL;
	news->prev = NULL;
	news->data = x;

	return news;
}

//链表初始化
void Initialize(Pointdef* head)
{
	head->next = head;
	head->prev = head;
}

//链表打印
void Printf_t(Pointdef* head)
{
	Pointdef* tail = head->next;

	while (tail != head)
	{
		printf("%d <= ", tail->data);
		tail = tail->next;
	}
	printf("NULL\n");
}

//在目标节点前面插入
void FrontInsertion(Pointdef* tail ,int x)
{
	
	assert(tail);

	Pointdef* prev = tail->prev;
	Pointdef* news = Newspoint(x);

	prev->next = news;
	news->prev = prev;

	news->next = tail;
	tail->prev = news;
	
}

//在目标节点后面插入
void OutInsertion(Pointdef* tail, int x)
{
	assert(tail);
	//目标节点的下一个节点不能是空,否则就是尾插了
	assert(tail->next);

	Pointdef* news = Newspoint(x);
	Pointdef* next = tail->next;

	tail->next = news;
	news->prev = tail;

	news->next = next;
	next->prev = news;
}

//链表头删
void Outomit(Pointdef* head,int x)
{
	assert(head);
	assert(head->next);

	Pointdef* tail = head->next->next;
	Pointdef* next = head->next;

	head->next = tail;
	tail->prev = head;

	free(next);
	next = NULL;
}

//链表尾删
void Tailomit(Pointdef* head, int x)
{
	assert(head);

	Pointdef* prev = head->prev->prev;
	Pointdef* tail = head->prev;
	
	prev->next = head;
	head->prev = prev;

	free(tail);
	tail = NULL;
}

//链表头插
void Headinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->next;
	Pointdef* news = Newspoint(x);

	head->next = news;
	news->prev = head;

	news->next = tail;
	tail->prev = news;
}

//链表尾插
void Tailinsert(Pointdef* head, int x)
{
	assert(head);

	Pointdef* tail = head->prev;
	Pointdef* news = Newspoint(x);

	tail->next = news;
	news->prev = tail;

	head->prev = news;
	news->next = head;
}

//链表中间节点删除
void Omit(Pointdef* tail)
{
	Pointdef* pc = tail->prev;
	Pointdef* pt = tail->next;

	pc->next = pt;
	pt->prev = pc;

	free(tail);
	tail = NULL;
}

//双链表销毁
void Undermine(Pointdef* head)
{
	assert(head);

	Pointdef* cur = head->next;
	Pointdef* tail = cur->next;

	while (cur != head)
	{
		tail = cur->next;

		free(cur);
		cur = tail;
	}
	free(head);
	head = NULL;

	printf("释放完毕\n");
}

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

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

相关文章

Docker 之mysql从头开始——Docker下mysql安装、启动、配置、进入容器执行(查询)sql

一、Docker 之mysql安装配置 步骤一&#xff1a;拉取镜像 1. 查看是否包含已安装的mysql。 docker images | grep mysql 2. 如上图所示&#xff0c;我们有mysql镜像&#xff0c;所以不必对mysql镜像进行拉取&#xff0c;如若没有上图中的惊喜&#xff0c;使用如下命令进行拉取…

网易日常实习一面面经

1. 自我介绍 2. 两道代码题&#xff1a; 第一道题&#xff1a;写一道链表排序题要求空间复杂度O(1) &#xff1a;已ac 插入排序算法 时间复杂度 O(N^2)&#xff0c;空间复杂度O(1) class ListNode{int val;ListNode next;public ListNode(int x) {this.val x;} } public cl…

DeepSeek LLM 论文解读:相信长期主义开源理念可扩展大语言模型(DeepSeek 吹响通用人工智能的号角)

论文链接&#xff1a;DeepSeek LLM: Scaling Open-Source Language Models with Longtermism&#xff08;相信长期主义开源理念可扩展大语言模型&#xff09; 目录 摘要一、数据处理&#xff08;一&#xff09;数据清洗与丰富&#xff08;二&#xff09;分词器与词汇设置 二、模…

02DevOps基础环境准备

准备两台Linux的操作系统&#xff0c;最简单的方式就是在本机上使用虚拟机搭建两个操作系统&#xff08;实际生产环境是两台服务器&#xff0c;虚拟机的方式用于学习使用&#xff09; 我搭建的两台服务器的ip分别是192.168.1.10、192.168.1.11 192.168.1.10服务器用于安装doc…

基于 SpringBoot 和 Vue 的智能腰带健康监测数据可视化平台开发(文末联系,整套资料提供)

基于 SpringBoot 和 Vue 的智能腰带健康监测数据可视化平台开发 一、系统介绍 随着人们生活水平的提高和健康意识的增强&#xff0c;智能健康监测设备越来越受到关注。智能腰带作为一种新型的健康监测设备&#xff0c;能够实时采集用户的腰部健康数据&#xff0c;如姿势、运动…

表单与交互:HTML表单标签全面解析

目录 前言 一.HTML表单的基本结构 基本结构 示例 二.常用表单控件 文本输入框 选择控件 文件上传 按钮 综合案例 三.标签的作用 四.注意事项 前言 HTML&#xff08;超文本标记语言&#xff09;是构建网页的基础&#xff0c;其中表单&#xff08;<form>&…

vue3中使用print-js组件实现打印操作

第一步&#xff1a;安装依赖 yarn add print-js 第二步&#xff1a;创建打印组件&#xff1a;PrintHtmlComp.vue <template><div id"printArea_123456789"><!-- 默认插槽&#xff0c;传入打印内容 --><slot></slot></div>…

【计算机网络】TCP/IP 网络模型有哪几层?

目录 应用层 传输层 网络层 网络接口层 总结 为什么要有 TCP/IP 网络模型&#xff1f; 对于同一台设备上的进程间通信&#xff0c;有很多种方式&#xff0c;比如有管道、消息队列、共享内存、信号等方式&#xff0c;而对于不同设备上的进程间通信&#xff0c;就需要网络通…

网络工程师 (29)CSMA/CD协议

前言 CSMA/CD协议&#xff0c;即载波监听多路访问/碰撞检测&#xff08;Carrier Sense Multiple Access with Collision Detection&#xff09;协议&#xff0c;是一种在计算机网络中&#xff0c;特别是在以太网环境下&#xff0c;用于管理多个设备共享同一物理传输介质的重要…

基于Python的人工智能驱动基因组变异算法:设计与应用(下)

3.3.2 数据清洗与预处理 在基因组变异分析中,原始数据往往包含各种噪声和不完整信息,数据清洗与预处理是确保分析结果准确性和可靠性的关键步骤。通过 Python 的相关库和工具,可以有效地去除噪声、填补缺失值、标准化数据等,为后续的分析提供高质量的数据基础。 在基因组…

AI大语言模型

一、AIGC和生成式AI的概念 1-1、AIGC Al Generated Content&#xff1a;AI生成内容 1-2、生成式AI&#xff1a;generative ai AIGC是生成式 AI 技术在内容创作领域的具体应用成果。 目前有许多知名的生成式 AI&#xff1a; 文本生成领域 OpenAI GPT 系列百度文心一言阿里通…

在postman中设置环境变量和全局变量以及五大常用响应体断言

一、什么是环境变量和全局变量 环境变量&#xff08;Environment Variables&#xff09;和全局变量&#xff08;Global Variables&#xff09;是 Postman 中用于存储和管理数据的两种变量类型&#xff0c;它们可以提高 API 测试的灵活性和可维护性。 1、 环境变量&#xff08…

Redis数据库(二):Redis 常用的五种数据结构

Redis 能够做到高性能的原因主要有两个&#xff0c;一是它本身是内存型数据库&#xff0c;二是采用了多种适用于不同场景的底层数据结构。 Redis 常用的数据结构支持字符串、列表、哈希表、集合和有序集合。实现这些数据结构的底层数据结构有 6 种&#xff0c;分别是简单动态字…

C++STL(六)——list模拟

目录 本次所需实现的三个类一、结点类的模拟实现构造函数 二、迭代器类的模拟实现为什么有迭代器类迭代器类的模板参数说明构造函数运算符的重载- -运算符的重载和!运算符的重载*运算符的重载->运算符的重载引入模板第二个和第三个参数 三、list的模拟实现3.1 默认成员函数构…

国产编辑器EverEdit - 替换功能详解

1 替换 1.1 应用场景 替换文本是在文档编辑过程中不可回避的操作&#xff0c;是将指定的关键词替换为新的文本&#xff0c;比如&#xff1a;写代码时修改变量名等。 1.2 使用方法 1.2.1 基本替换 使用主菜单查找 -> 替换&#xff0c;或使用快捷键Ctrl H&#xff0c;会打…

LIMO:上海交大的工作 “少即是多” LLM 推理

25年2月来自上海交大、SII 和 GAIR 的论文“LIMO: Less is More for Reasoning”。 一个挑战是在大语言模型&#xff08;LLM&#xff09;中的复杂推理。虽然传统观点认为复杂的推理任务需要大量的训练数据&#xff08;通常超过 100,000 个示例&#xff09;&#xff0c;但本文展…

防御保护作业二

拓扑图 需求 需求一&#xff1a; 需求二&#xff1a; 需求三&#xff1a; 需求四&#xff1a; 需求五&#xff1a; 需求六&#xff1a; 需求七&#xff1a; 需求分析 1.按照要求进行设备IP地址的配置 2.在FW上开启DHCP功能&#xff0c;并配置不同的全局地址池&#xff0c;为…

蓝桥与力扣刷题(226 翻转二叉树)

题目&#xff1a;给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1]示例 2&#xff1a; 输入&#xff1a;root [2,1,3] 输出&#xff1a;[2,…

大型语言模型(LLM)中的自适应推理预算管理:基于约束策略优化的解决方案

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

[EAI-033] SFT 记忆,RL 泛化,LLM和VLM的消融研究

Paper Card 论文标题&#xff1a;SFT Memorizes, RL Generalizes: A Comparative Study of Foundation Model Post-training 论文作者&#xff1a;Tianzhe Chu, Yuexiang Zhai, Jihan Yang, Shengbang Tong, Saining Xie, Dale Schuurmans, Quoc V. Le, Sergey Levine, Yi Ma 论…