双向链表 -- 详细理解和实现

                                                                                         欢迎光顾我的homepage                                                              

前言

        双向链表是一种带头双向循环的链表。在双向链表中，首先存在着一个头结点；其次每个节点有指向下一个节点的指针next 和指向上一个节点的指针prev ；最后，双向链表的头结点中存放上一个节点的指针指向链表的尾节点，尾节点中存放下一个节点的指针指向链表的头结点，形成一个闭环。这样双向链表既可以从前遍历，也可以从后遍历，直到回到起点。

一、链表的分类

        链表的结构多种多样，链表呢可以是带头（不带头）、双向（单向）、循环（不循环）的，我们之前实现的单链表其实就是不带头，单向，不循环的链表。

而这些有什么区别呢？

        带头和不带头

这里带头和不带头指的是有没有头结点，这单链表的实现过程中，是直接创建一个指针变量指向链表的第一个节点（这是没有头结点的情况），而存在头结点呢，就是一个哨兵位，里面没有存放数据，存放了指向第一个节点的指针。

        可以看到，带头的链表多了一个节点（head），这个节点中没有存放任何数据，这样做可以方便对链表的节点进行统一操作。

        单向和双向

    单向是可以通过一个节点找到它的后一个节点，而双向是可以通过一个节点找到它前后的节点。

        循环和不循环

    这实现单链表的时候，我们将链表的最后一个节点next指针置位了空指针（NULL），而循环的链表中，我们会将最后一个节点的next指针指向链表的头结点，对于双向链表，将头节点的prev(上一个节点）指针指向链表的尾节点。

二、双向链表的实现

这里实现的双向链表，先来看一下双向链表的节点结构

双向链表节点

typedef int LTDataType;
//双向链表
typedef struct ListNode
{struct ListNode* prev;  //指向上一个节点struct ListNode* next;  //指向下一个节点LTDataType data;
}LTNode;

双向链表的功能预览

//初始化并创建头结点
void LTInit(LTNode** phead);
//LTNode* LTInit();
//输出
void LTPrint(LTNode* phead);
//创建新的节点
LTNode* LTBuyNode(LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType find);
//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x);
//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x);
//删除pos节点
void LTPop(LTNode* pos);
//链表销毁
void LTDesTroy(LTNode* phead);

2.1、创建新的节点

        创建节点，和单链表一样，都是动态开辟的空间。

//创建新的节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* ptail = (LTNode*)malloc(sizeof(LTNode));if (ptail == NULL){perror("LTBuyNode--malloc filed!");exit(1);}ptail->data = x;ptail->prev = ptail->next = NULL;return ptail;
}

2.2、双向链表初始化并创建头结点

        链表初始化，其实就是创建一个头节点（也叫哨兵位）；因为这里是双向链表，创建完头节点之后，让头节点的prev和next指针都指向它自己。

//初始化并创建头结点
void LTInit(LTNode** phead)
{*phead = LTBuyNode(-1);(*phead)->prev = (*phead)->next = *phead;
}

2.3、输出链表

        遍历链表并输出有效数据，这里双向链表可以从前开始遍历也可以从后开始遍历。

//输出
void LTPrint(LTNode* phead)
{LTNode* ptail = phead->next;//遍历双向链表 -- 从前开始遍历while (ptail != phead){printf("%d -> ", ptail->data);ptail = ptail->next;}printf("\n");
}

2.4、双向链表头插数据

        从链表的头部插入数据，创建新的节点，然后将新的节点prev指针指向头节点，将next指针指向头节点的下一个节点；然后修改头节点的next指针和头节点下一个节点的prev指针即可。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;//修改前后节点的指针指向phead->next->prev = newnode;phead->next = newnode;
}

2.5、双向链表尾插数据

        从链表尾部插入到尾节点的后面，创建新的节点，将新节点的prev指针指向头节点的上一个节点，将next指针指向头节点，然后修改尾节点的next指针和头节点的prev指针即可。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;//修改前后节点指针指向phead->prev->next = newnode;phead->prev = newnode;
}

2.6、双向链表头删数据

        头删是删除头节点的后一个节点，因为是动态开辟的内存，需要内存释放；删除后，让头节点的next指针 指向下一个数据的节点。

//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead != phead->next); //链表为空的话就不能进行删除LTNode* del = phead->next;  phead->next->next->prev = phead;phead->next = phead->next->next;free(del);del = NULL;
}

2.7、双向链表尾删数据

        尾插是删除链表的尾节点，释放内存之后，让尾节点的上一个节点next指针指向头节点，头节点的prev指针指向删除节点的上一个节点。

//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead); //链表为空不能进行删除LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

2.8、双向链表查找数据

        这里如果找到了，就返回该节点的指针，如果没有就返回NULL；方便对其进行前后插入数据和删除。

//查找
LTNode* LTFind(LTNode* phead, LTDataType find)
{assert(phead);LTNode* ptail = phead->next;while (ptail != phead) //遍历链表{if (ptail->data == find) {return ptail;}ptail = ptail->next;}return NULL;
}

2.9、在指定节点pos之前插入数据

        根据我们查找到的节点，在其之前插入数据，首先创建新节点，将新节点的prev指针指向pos的前一个节点，新节点的next指针指向pos；再修改pos的上一个节点的next指针指向和pos的prev指针指向即可；

//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;//修改pos前后节点指针的指向pos->prev->next = newnode;pos->prev = newnode;
}

        这里就可以发现双向链表的一个好处，不用像单向链表那样遍历链表来寻找pos的上一个节点。

2.10、在指定节点pos之后插入数据

        根据查找到的节点，在其之后插入数据；首先创建节点，将新节点的prev指针指向pos，新节点的next指针指向pos的下一个节点；然后修改pos的next指针指向和pos下一个节点的prev指针指向即可。

//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;//修改pos前后节点指针的指向pos->next->prev = newnode;pos->next = newnode;
}

2.11、删除指定节点pos

        根据查找到的节点，然后将其删除，这里需要修改pos前后节点的指针指向。

//删除pos节点
void LTPop(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.12、双向链表的销毁

        及时对动态开辟的内存进行释放，养成好习惯

        现在，动态开辟的链表需要进行销毁（也就是动态内存释放），这里就需要遍历链表了。

//链表销毁
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* ptail = phead->next;while (ptail != phead){LTNode* del = ptail->next;free(ptail);ptail = del;}free(ptail);ptail = NULL;
}


代码总览

List.h

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//双向链表
typedef struct ListNode
{struct ListNode* prev;  //指向上一个节点struct ListNode* next;  //指向下一个节点LTDataType data;
}LTNode;//初始化并创建头结点
void LTInit(LTNode** phead);
//LTNode* LTInit();
//输出
void LTPrint(LTNode* phead);
//创建新的节点
LTNode* LTBuyNode(LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType find);
//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x);
//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x);
//删除pos节点
void LTPop(LTNode* pos);
//链表销毁
void LTDesTroy(LTNode* phead);

List.c

#include"List.h"//创建新的节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* ptail = (LTNode*)malloc(sizeof(LTNode));if (ptail == NULL){perror("malloc filed!");exit(1);}ptail->data = x;ptail->prev = ptail->next = NULL;return ptail;
}
//初始化并创建头结点
void LTInit(LTNode** phead)
{*phead = LTBuyNode(-1);(*phead)->prev = (*phead)->next = *phead;
}
//输出
void LTPrint(LTNode* phead)
{LTNode* ptail = phead->next;//遍历双向链表 -- 从前开始遍历while (ptail != phead){printf("%d -> ", ptail->data);ptail = ptail->next;}printf("\n");
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead;newnode->next = phead->next;//修改前后节点的指针指向phead->next->prev = newnode;phead->next = newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;//修改前后节点指针指向phead->prev->next = newnode;phead->prev = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead != phead->next); //链表为空的话就不能进行删除LTNode* del = phead->next;  phead->next->next->prev = phead;phead->next = phead->next->next;free(del);del = NULL;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead); //链表为空不能进行删除LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType find)
{assert(phead);LTNode* ptail = phead->next;while (ptail != phead) //遍历链表{if (ptail->data == find) {return ptail;}ptail = ptail->next;}return NULL;
}
//在pos节点之前插入数据
void LTPush(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos;newnode->prev = pos->prev;//修改pos前后节点指针的指向pos->prev->next = newnode;pos->prev = newnode;
}
//在pos节点之后插入数据
void LTPushAfter(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;//修改pos前后节点指针的指向pos->next->prev = newnode;pos->next = newnode;
}

感谢各位大佬支持并指出问题，

                如果本篇内容对你有帮助，可以一键三连支持以下，感谢支持！！！

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

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

相关文章

MySQL安全值守常用语句

MySQL安全值守常用语句

一、用户权限设置 1、Mysql中用户是如何定义的 用户名主机域 10.0.0.5110.0.0.%%10.0.0.0/255.255.255.0Db01Localhost127.0.0.1 2、用户创建 create user xinjing% identified by 123 3、用户删除 drop user username&#xff1b;username 是要删除的用户名:如 drop user root…
阅读更多...
Docker 基本管理及部署

Docker 基本管理及部署

目录 1.Docker概述 1.1 Docker是什么&#xff1f; 1.2 Docker的宗旨 1.3 容器的优点 1.4 Docker与虚拟机的区别 1.5 容器在内核中支持的两种技术 1.6 namespace的六大类型 2.Docker核心概念 2.1 镜像 2.2 容器 2.3 仓库 3.安装Docker 3.1 查看 docker 版本信息 4.…
阅读更多...
SpringBoot新手快速入门系列教程十：基于docker容器，部署一个简单的项目

SpringBoot新手快速入门系列教程十：基于docker容器，部署一个简单的项目

前述&#xff1a; 本篇教程将略过很多docker下载环境配置的基础步骤&#xff0c;如果您对docker不太熟悉请参考我的上一个教程&#xff1a;SpringBoot新手快速入门系列教程九&#xff1a;基于docker容器&#xff0c;部署一个简单的项目 使用 Docker Compose 支持部署 Docker 项…
阅读更多...
LLM基础模型系列：Fine-Tuning总览

LLM基础模型系列：Fine-Tuning总览

由于对大型语言模型&#xff0c;人工智能从业者经常被问到这样的问题&#xff1a;如何训练自己的数据&#xff1f;回答这个问题远非易事。生成式人工智能的最新进展是由具有许多参数的大规模模型驱动的&#xff0c;而训练这样的模型LLM需要昂贵的硬件&#xff08;即许多具有大量…
阅读更多...
51单片机(STC8051U34K64)_RA8889_SPI4参考代码（v1.3)

51单片机(STC8051U34K64)_RA8889_SPI4参考代码（v1.3)

硬件&#xff1a;STC8051U34K64 RA8889开发板&#xff08;硬件跳线变更为SPI-4模式&#xff0c;PS101&#xff0c;R143&#xff0c;R141短接&#xff0c;R142不接&#xff09; STC8051U34K64是STC最新推出来的单片机&#xff0c;主要用于替换传统的8051单片机&#xff0c;与标…
阅读更多...
达梦数据库中的线程和进程

达梦数据库中的线程和进程

达梦数据库中的线程和进程 在达梦数据库中&#xff0c;线程和进程的概念与操作系统中的定义类似&#xff0c;但有一些特定的实现细节和用途。以下是达梦数据库中线程和进程的一些关键点&#xff1a; 进程&#xff08;Process&#xff09;&#xff1a; 在达梦数据库中&#x…
阅读更多...
oracle哪些后台进程不能杀？

oracle哪些后台进程不能杀？

oracle 有很多的后台进程&#xff0c;在遇到特殊情况的时候如锁表&#xff0c;如果等待的是一个后台进程&#xff0c;那这时就需要考量是不是能杀掉这个后台进程&#xff1f;杀掉这个后台进程会不会引起实例崩溃&#xff1f;本着实践出真知&#xff0c;本文针对oracle 11g&…
阅读更多...
RK3588编译rkmpp，拉取海康威视网络摄像头264码流并运行yolo

RK3588编译rkmpp，拉取海康威视网络摄像头264码流并运行yolo

硬件&#xff1a;EVB评估版 SOC&#xff1a;Rockchip RK3588 背景&#xff1a; 由于项目需要&#xff0c;需要拉取264码流&#xff0c;并通过将yolov5s.pt将模型转化为rknn模型&#xff0c;获取模型分析结果。取流可以通过软件解码或者硬件解码&#xff0c;硬件解码速度更快&…
阅读更多...
插片式远程 I/O模块：热电阻温度采集模块与PLC配置案例

插片式远程 I/O模块：热电阻温度采集模块与PLC配置案例

XD系列成套系统主要由耦合器、各种功能I/O模块、电源辅助模块以及终端模块组成。有多种通讯协议总线的耦合器&#xff0c;例如Profinet、EtherCAT、Ethernet/IP、Cclink IE以及modbus/TCP等。I/O 模块可分为多通道数字量输入模块、数字量输出模块、模拟量输入模块、模拟量输出模…
阅读更多...
[leetcode]minimum-cost-to-reach-destination-in-time 规定时间内到达终点的最小费用

[leetcode]minimum-cost-to-reach-destination-in-time 规定时间内到达终点的最小费用

. - 力扣&#xff08;LeetCode&#xff09; class Solution { private:// 极大值static constexpr int INFTY INT_MAX / 2;public:int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {int n passingFees.size();ve…
阅读更多...
2024年文化研究与数字媒体国际会议 (CRDM 2024)

2024年文化研究与数字媒体国际会议 (CRDM 2024)

2024年文化研究与数字媒体国际会议 (CRDM 2024) 2024 International Conference on Cultural Research and Digital Media 【重要信息】 大会地点&#xff1a;珠海 大会官网&#xff1a;http://www.iccrdm.com 投稿邮箱&#xff1a;iccrdmsub-conf.com 【注意&#xff1a;稿将…
阅读更多...
STL（一）

STL（一）

书写形式&#xff1a;string (const string& str, size_t pos, size_t len npos); 举例&#xff1a; int main(){ string url("https://mp.csdn.net/mp_blog/creation/editor?spm1000.2115.3001.4503") string sub1(url,0,5);//从下标为0开始向后5个字符&…
阅读更多...
Hvv工具推荐——IWannaGetAll

Hvv工具推荐——IWannaGetAll

OA基本上是每次hvv中都会被突破的&#xff0c;基本上也都会爆出各种各样的0day&#xff0c;如果真的0day防不住&#xff0c;那我们必须要把1day、nday做一遍检查。 IWannaGetAll 是一款专门针对主流OA&#xff08;办公自动化&#xff09;系统的漏洞检测和利用工具。 IWannaGe…
阅读更多...
【正点原子K210连载】第二十一章 machine.UART类实验摘自【正点原子】DNK210使用指南-CanMV版指南

【正点原子K210连载】第二十一章 machine.UART类实验摘自【正点原子】DNK210使用指南-CanMV版指南

1&#xff09;实验平台&#xff1a;正点原子ATK-DNK210开发板 2&#xff09;平台购买地址https://detail.tmall.com/item.htm?id731866264428 3&#xff09;全套实验源码手册视频下载地址&#xff1a; http://www.openedv.com/docs/boards/xiaoxitongban 第二十一章 machine.…
阅读更多...
05：定时器中断

05：定时器中断

中断 1、定时器T0中断2、案例&#xff1a;通过定时器T0中断来实现灯间隔1s亮灭 1、当中央处理机CPU正在处理某件事的时候外界发生了紧急事件请求&#xff0c;要求CPU暂停当前的工作&#xff0c;转而去处理这个紧急事件&#xff0c;处理完以后&#xff0c;再回到原来被中断的地方…
阅读更多...
Android 使用 Debug.startMethodTracing 分析方法耗时

Android 使用 Debug.startMethodTracing 分析方法耗时

参考 Generate Trace Logs by Instrumenting Your App 官网提供了 trace 工具来分析方法耗时。 生成 trace 文件 package com.test.luodemo.trace;import androidx.appcompat.app.AppCompatActivity;import android.os.Bundle; import android.os.Debug; import android.uti…
阅读更多...
Elasticsearch：Node.js ECS 日志记录 - Winston

Elasticsearch：Node.js ECS 日志记录 - Winston

这是继上一篇文章 “Elasticsearch&#xff1a;Node.js ECS 日志记录 - Pino” 的续篇。我们继续上一篇文章来讲述使用 Winston 包来针对 Node.js 应用生成 ECS 向匹配的日子。此 Node.js 软件包为 winston 记录器提供了格式化程序&#xff0c;与 Elastic Common Schema (ECS) …
阅读更多...
axios使用sm2加密数据后请求参数多了双引号解决方法

axios使用sm2加密数据后请求参数多了双引号解决方法

axios使用sm2加密数据后请求参数多了双引号解决 背景问题描述解决过程 背景 因项目安全要求&#xff0c;需对传给后端的入参加密&#xff0c;将请求参数加密后再传给后端 前期将axios降低到1.6.7后解决了问题&#xff0c;但最近axios有漏洞&#xff0c;安全要求对版本升级&…
阅读更多...
软航文档控件VUE示例运行及控件替换方法记录

软航文档控件VUE示例运行及控件替换方法记录

目录 示例运行 步骤一、npm install 步骤二、npm run dev 软航文档控件替换 附 vue小白记录一下软航文档控件VUE示例的运行方法以及示例中控件的替换过程。 示例运行 在已经安装好VUE环境的电脑上&#xff0c;VUE环境部署可以参考另一篇&#xff1a;配置VUE环境过程中 …
阅读更多...
PHP红包拓客微信小程序系统源码

PHP红包拓客微信小程序系统源码

&#x1f389;红包狂欢&#xff0c;客源滚滚来&#xff01;红包拓客微信小程序&#xff0c;营销新利器&#x1f680; &#x1f9e7;一、创意红包&#xff0c;吸引眼球 你还在为如何吸引顾客而烦恼吗&#xff1f;红包拓客微信小程序来帮你&#xff01;&#x1f381; 它以创意红…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023