数据结构-双链表

学习完单链表,现在继续学习双链表

一、双链表结构

带头双向循环链表(简称:双链表)

注意:这⾥的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头节点。

带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这⾥“放哨 的” “哨兵位”存在的意义: 遍历循环链表避免死循环

二、双链表的实现

定义双链表节点结构

与单链表相比,双链表由于是双向的,因此它多了一个前驱指针

typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//保存指向前一个节点的指针struct ListNode* next;//指向下一个节点的指针
}LTNode;

说明

双链表是带头链表,即它的头节点(哨兵节点)是不可变的,它作用是站岗放哨,为后续的有效节点标明位置,因此,与单链表不同的是,双链表在函数传参的过程中传的是一级指针,不再是二级指针(保证哨兵节点不可改变)

在接下来的双链表实现中,为保持接口一致性,全部传一级指针

双链表初始化 InitList

单链表为空的意思就是空链表,链表内无任何节点,而双链表为空时,此时链表中只剩下一个头节点(哨兵节点),无有效节点,代表双链表为空的意思

因此,在插入数据之前,双链表必须初始化到只有一个头结点的情况

创建一个函数LTBuyNode,表示申请节点,在初始化时给链表申请一个哨兵节点

思考一下,是否可以将哨兵节点的prev指针和next指针初始化为NULL?显然是不可以的

双链表是循环链表,它的首尾相连的,因此,链表的prev指针和next指针应该在初始化时指向哨兵节点本身

//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if(node == NULL){perror("LTBuyNode-malloc");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
//初始化 - 传一级指针的写法
LTNode* InitList()
{LTNode* phead = LTBuyNode(-1);//也可以传其他数字,表示初始化哨兵节点为某一个值return phead;
}//初始化 - 传二级指针的写法
void InitList(LTNode** pphead)
{//给双链表创建一个哨兵节点*pphead = LTBuyNode(-1);
}

测试:

//初始化
LTNode* plist = InitList();//LTNode* plist = NULL;
//InitList(&plist);

打印链表 LTPrint

打印链表的步骤基本上和单链表相同,但是要注意,打印双链表的节点时,哨兵节点并不需要打印出来,是从链表的第一个有效节点开始打印(即哨兵节点的后一个节点);

在while循环条件部分不同:双链表头尾相连,如果按照单链表的循环条件pcur进行打印,会陷入无限循环,因此,我们要在尾节点的next指针为头节点时,停止打印

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while(pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;}printf("\n");
}

尾部插入/头部插入

尾插 LTPushBack

我们知道,链表的尾节点的next指针就是头节点phead(尾节点->next=phead),头节点phead的prev指针就是尾节点(即phead->prev=尾节点)【首尾相连】,我们要做的就是将创建的新节点newnode尾插到原链表的尾部作为新的尾节点并与头节点首尾相连。

首先要做的是将newnode尾插到原链表中,将newnode的prev指针指向phead->prev(原尾节点),然后将newnode的next指针指向头节点phead,这样就将newnode节点插入到了原链表中

接着更新新的尾节点与头节点头尾相连,将原链表的尾节点phead->prev的next指针指向newnode,然后newnode成为新的尾节点 phead->prev

void LTPushBack(LTNode* phead,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//1.先在尾部插入新节点newnode->prev = phead->prev;newnode->next = phead;//2.更新新的尾节点与头节点进行首尾相连phead->prev->next = newnode;phead->prev = newnode;
}

头插 LTPushFront

要注意,我们所说的头插是头插到第一个有效节点的前面,即头节点(哨兵节点)的后面

(将新节点插入到哨兵节点前面,就是尾插)

首先还是将新节点newnode插入到原链表中,将newnode插入到头节点phead和第一个有效节点phead->next之间,然后更新newnode为新的第一个有效节点:

将phead->next(原第一个有效节点)的prev指针指向newnode,再将newnode的prev指针指向phead,或者先将newnode的prev指针指向phead,再通过newnode找到原第一个有效节点(newnode->next),将newnode->next的prev指针指向newnode

void LTPushFront(LTNode* phead,LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//1.先在头节点和第一个有效节点之间插入一个新节点,表示头插newnode->next = phead->next;newnode->prev = phead;//2.更新新的节点为新的第一个有效节点phead->next->prev = newnode;phead->next = newnode;//phead->next = newnode;//newnode->next->prev = newnode;
}

尾部删除/头部删除

尾删 LTPopBack

能够进行尾删的条件:链表有效且链表不能为空(只有一个哨兵节点)

要将尾节点(phead->prev)删除,将它的前一个节点phead->prev->prev变成新的尾节点:将phead->prev->prev的next指针指向phead,将phead的prev指针指向phead->prev->prev,然后将原尾节点释放掉

但是,要注意,此时已经找不到原尾节点的位置了,无法进行释放操作,因此,在进行以上操作前,先将原尾节点phead->prev存放在一个指针变量del中

void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}

头删 LTPopFront

能够进行头删的条件:链表有效且链表不能为空

头删是删除链表的第一个有效节点,使第二个有效节点成为新的第一个有效节点

首先先将要删除的phead->next节点存放在指针del中,然后将phead的next指针改为del->next(第二个有效节点),再将del->next的prev指针指向phead,然后将del释放掉

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

查找链表 LTFind

通过遍历链表找到想要找的节点数据,如果找到了,返回这个节点的指针,如果没有找到,返回NULL

LTNode* LTFind(LTNode* phead,LTDataType x)
{LTNode* pcur = phead->next;while(pcur != phead){if(pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

在pos位置之后插入数据 LTInsert

需要将新节点newnode插入在pos和pos->next之间,即先将newnode的prev指针指向pos,newnode的next指针指向pos->next,然后将newnode节点变成新的pos->next节点

注意有一种情况:当pos的位置是尾节点时,就是要在phead->prev和phead之间插入数据,即尾插

但是我们在对该函数传参时,并不需要用到phead(在pos位置之后插入节点只需知道pos和pos->next,以及要插入的数据即可),因此,不能直接调用尾插函数。不过我们并不需要调用尾插函数也可以做到,因为将newnode插入pos和pos->next之间的做法也适用于尾插的情况

这里不再画图讲解

void LTInsert(LTNode* pos,LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

在pos位置之前插入数据 LTInsertBefort

需要将newnode节点插入在pos->prev与pos之间,先将newnode的prev指针指向pos->prev,再将newnode的next指针指向pos,表示插入新节点成功,当然,这也有一种情况:当pos的围位置是第一个有效节点时,就是头插的方法,不过我们也不需要调用函数使用,因为以上的操作已经覆盖了头插做法

void LTInsertBefort(LTNode* pos,LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}

删除pos节点

删除pos节点,直接修改pos->next的prev指针为pos->prev,pos->prev的next指针为pos->next,然后将pos节点释放掉即可

void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

销毁链表 LTDestroy

在遍历销毁链表之前,应该保存一下下一个节点的指针,避免后续找不到位置

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}
注意

LTErase 和 LTDestroy 函数参数理论上要传二级指针,因为我们需要让形参的改变影响到实参,但为了保持接口一致性传一级指针,传一级指针存在的问题:当形参phead置为NULL后,实参plist不会被修改为NULL,因此解决办法:调用完方法后手动将实参置为NULL

//测试删除pos节点
LTErase(find);
find = NULL;
LTPrint(plist);//销毁链表
LTDestroy(plist);
plist = NULL;

三、完整代码

List.h#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//声明双向链表中提供的方法
//初始化
//void InitList(LTNode** pphead); 
LTNode* InitList();//打印链表
void LTPrint(LTNode* phead);//在插入数据之前,链表必须初始化到只有一个头结点的情况
//不改变哨兵位的地址,因此传一级指针即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//在pos位置之前插入数据
void LTInsertFront(LTNode* pos, LTDataType x);//删除pos节点
void LTErase(LTNode* pos);//销毁链表
void LTDestroy(LTNode* phead);
List.c#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
//初始化
//void InitList(LTNode** pphead)
//{
//	//给双链表申请一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* InitList()
{LTNode* phead = LTBuyNode(-1);return phead;
}
//打印链表
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x) //将新节点插入到头节点的前面,即尾插
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnode//1.先在尾部插入新节点newnode->prev = phead->prev;newnode->next = phead;//2.更新新的尾节点与头节点进行首尾相连phead->prev->next = newnode;phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x) //头插,要往头节点后面插入
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->next//1.先在头节点和第一个有效节点之间插入一个新节点,表示头插newnode->next = phead->next;newnode->prev = phead;//2.更新新的节点为新的第一个有效节点phead->next->prev = newnode;phead->next = newnode;//也可以这样写/*phead->next = newnode;newnode->next->prev = newnode;*/
}
//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}
//在pos位置之前插入数据
void LTInsertFront(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos->prev newnode posnewnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead,但是没有参数phead,无法增加校验assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}
//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}
test.c#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"void ListTest01()
{//初始化/*LTNode* plist = NULL;InitList(&plist);*/LTNode* plist = InitList();//测试尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);//测试头插/*LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);*///测试尾删/*LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);*///测试头删/*LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);*///测试查找链表LTNode* find = LTFind(plist, 2);/*if (find == NULL){printf("找不到\n");}else{printf("找到了\n");}*///测试在pos位置之后插入数据/*LTInsert(find, 66);LTPrint(plist);*///测试在pos位置之前插入数据/*LTInsertFront(find, 88);LTPrint(plist);*///测试删除pos节点LTErase(find);find = NULL;         //LTErase 和 LTDestroy 函数参数理论上要传二级指针,因为我们需要让形参的改变影响到实参,但为了保持接口一致性传LTPrint(plist);      //一级指针,传一级指针存在的问题:当形参phead置为NULL后,实参plist不会被修改为NULL,因此解决办法:调用完方法后//手动将实参置为NULL//销毁链表LTDestroy(plist);plist = NULL;
}
int main()
{ListTest01();return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

福彩双色球第2025090期篮球号码分析

明天是星期四&#xff0c;明天晚上双色球开奖。福彩双色球第2025090期篮球号码分析&#xff0c;上期开出号码05&#xff0c;数字形式是质数奇数2路球&#xff0c;小号0字头数字。本期篮球号码分析&#xff0c;篮球2尾数0212遗漏6期上次遗漏27期&#xff0c;篮球3尾数0313遗漏4期…

Python爬虫实战:研究Photon工具,构建企业信息收集系统

1. 引言 1.1 研究背景 在数字化时代,互联网作为全球最大的信息载体,涵盖商业情报、学术资源、公共信息等多个领域,对企业决策、学术研究和社会治理具有重要参考价值。传统信息获取方式依赖人工检索和简单脚本爬取,存在效率低下、覆盖范围有限、数据处理能力不足等问题。 …

Python Pandas.lreshape函数解析与实战教程

Python Pandas.lreshape 函数解析与实战教程 摘要 本教程旨在提供一份关于Pandas库中 pandas.lreshape 函数的全面使用教程和分析。lreshape 是一个用于数据重塑(Data Reshaping)的工具,具体而言,它擅长将“宽格式”(Wide Format)数据转换为“长格式”(Long Format)数…

vue3 el-dialog自定义实现拖拽、限制视口范围增加了拖拽位置持久化的功能

采用element-plus的拖拽功能代码,在此基础上增加了记忆拖拽上次拖拽位置的功能,开袋即食; 前提:每次关闭弹窗都要销毁; 解决了默认设置transform的偏移量后首次拖拽弹窗偏移量错误的问题修改。<template><el-dialogref="popupRefDialog":title="…

学习嵌入式之硬件——ARM体系

一、ARM内核基础知识1.ALU&#xff1a;算术逻辑单元&#xff1b;完成运算的电路2.通用寄存器&#xff1a;R0~R15R13&#xff08;SP&#xff09;&#xff1a;栈指针寄存器&#xff1a;指向栈顶的位置&#xff1b;并在函数调用、中断处理等场景中自动更新。R14&#xff08;LR&…

微信小程序中使用TensorFlowJS从环境搭建到模型训练及推理模型得到预测结果

1、小程序端环境准备app.json"plugins": {"tfjsPlugin": {"version": "0.2.0","provider": "wx6afed118d9e81df9"}}package.json"dependencies": {"tensorflow-models/posenet": "^2.2.…

深入剖析通用目标跟踪:一项综述

摘要 通用目标跟踪仍是计算机视觉领域一项重要且具有挑战性的任务,其难点在于复杂的时空动态变化,尤其在存在遮挡、相似干扰物和外观变化的情况下。过去二十年间,为应对这些挑战,研究者提出了多种跟踪范式,包括基于孪生网络的跟踪器、判别式跟踪器以及近期突出的基于Tran…

Next.js 链接与导航:页面间无缝切换

链接与导航&#xff1a;页面间无缝切换 关键要点 Next.js 提供了 <Link> 组件和程序化导航方法&#xff0c;实现页面间高效、无缝的切换。<Link> 组件利用客户端导航和预加载技术&#xff0c;优化用户体验和性能。程序化导航通过 useRouter 钩子&#xff08;Page…

根据经纬度(从nc格式环境数据文件中)提取环境因子

根据经纬度&#xff08;从nc格式环境数据文件中&#xff09;提取环境因子 文章目录前言一、准备所需文件二、代码分享总结前言 本文主要利用nc格式环境数据文件和物种经纬度分布文件&#xff0c;根据经纬度&#xff08;从nc格式环境数据文件中&#xff09;提取环境因子 一、准…

Uniapp 自定义 Tabbar 实现教程

Uniapp 自定义 Tabbar 实现教程1. 简介2. 实现步骤2.1 创建自定义 Tabbar 组件2.2 配置 pages.json3.1 路由映射3.2 样式设计3.3 图标处理4. 常见问题及解决方案4.1 页面跳转问题4.2 样式适配问题4.3 性能优化5. 扩展功能5.1 添加徽标5.2 添加动画效果6. 总结1. 简介 在 Uniap…

JuiceFS存储

因语雀与csdn markdown 格式有区别&#xff0c;请查看原文&#xff1a; https://www.yuque.com/dycloud/pss8ys 一、JuiceFS 介绍 1.1 JuiceFS 是什么 JuiceFS 是一款面向云环境设计的高性能 POSIX 文件系统&#xff0c;核心能力是将对象存储转化为全功能文件系统。它采用独…

【HarmonyOS Next之旅】DevEco Studio使用指南(三十八) -> 构建HAR

目录 1 -> 前言 2 -> 使用约束 3 -> 创建模块 4 -> 构建HAR 4.1 -> 以debug模式构建HAR 4.2 -> 以release模式构建HAR 4.3 -> 构建字节码格式的HAR 4.4 -> 对HAR进行签名 1 -> 前言 构建模式&#xff1a;DevEco Studio默认提供debug和rele…

93、【OS】【Nuttx】【构建】cmake menuconfig 目标

【声明】本博客所有内容均为个人业余时间创作&#xff0c;所述技术案例均来自公开开源项目&#xff08;如Github&#xff0c;Apache基金会&#xff09;&#xff0c;不涉及任何企业机密或未公开技术&#xff0c;如有侵权请联系删除 背景 接之前 blog 【OS】【Nuttx】【构建】cm…

React 表单处理:移动端输入场景下的卡顿问题与防抖优化方案

文章目录每日一句正能量前言一、问题场景与表现二、技术攻坚过程三、优化效果与经验沉淀每日一句正能量 山再高&#xff0c;往上攀&#xff0c;总能登顶&#xff1b;路再长&#xff0c;走下去&#xff0c;终将到达。每日一励&#xff0c;勇往直前。 前言 在移动端 React 项目开…

数据安全防护所需要的关键要素

数据安全防护是一个覆盖数据全生命周期&#xff08;采集、存储、传输、处理、销毁&#xff09;、融合技术、管理、流程与人员的系统性工程。其核心目标是保障数据的​​保密性&#xff08;Confidentiality&#xff09;、完整性&#xff08;Integrity&#xff09;、可用性&#…

【JavaEE】(8) 网络原理 HTTP/HTTPS

一、什么是 HTTP 协议 上节说到&#xff0c;应用层的协议需要约定通信的内容和数据格式。我们可以自定义应用层协议&#xff0c;也可以基于现成的应用层协议进行开发。协议的种类很多&#xff0c;最常见的之一就是 HTTP&#xff0c;广泛用于网站和手机 App。准确来说&#xff0…

C语言的数组与字符串练习题4

C语言的数组与字符串练习题4 16. 数组元素去重 题目描述: 编写一个C程序,输入一组整数存储在数组中,去除数组中的重复元素,并输出去重后的数组。 解题思路: 遍历数组,对于每个元素,检查它之前是否已经存在相同的元素。如果不存在,则将其保留;否则,跳过。可以使用一…

Transformers简单介绍 - 来源于huggingface

Transformers介绍 - 来源于huggingface 文章目录Transformers介绍 - 来源于huggingfaceTransformers能做什么pipeline()函数零样本分类推理API完形填空命名实体识别问答摘要提取翻译transformers是如何工作的transformers的具体组成注意力层机制transformers原始结构architectu…

template<typename R = void> 意义

在 C 中&#xff0c;template<typename R void> 表示定义一个模板参数 R&#xff0c;其默认类型为 void。这意味着&#xff1a;如果用户没有显式指定 R&#xff0c;则 R 默认为 void。如果用户显式指定了 R&#xff08;如 template<typename R void> 后面跟着 &l…

国产3D大型装配设计新突破①:图纸打开设计双加速 | 中望3D 2026

本文为CAD芯智库整理&#xff0c;未经允许请勿复制、转载&#xff01;在中望3D 2026的新版中&#xff0c;不仅在设计效率上进行了重大优化&#xff0c;更是在装配方面实现了突破性的改进&#xff0c;让每一个项目都能快速、精确地从概念变为现实。 中望3D2026亮点速递装配篇将…