【数据结构】双向带头循环链表的实现

前言：在前面我们学习了顺序表、单向链表，今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。

💖 博主CSDN主页:卫卫卫的个人主页 💞
👉 专栏分类:数据结构 👈
💯代码仓库:卫卫周大胖的学习日记💫
💪关注博主和博主一起学习!一起努力！
在这里插入图片描述

双向链表

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表(如下图所示)。通常我们会使用一个头节点head其并不存储数据只是作为一个哨兵位的作用负责指向下一个元素。在这里插入图片描述
双向链表的基本功能:

  1. 双向链表的初始化
  2. 双链表的销毁
  3. 创建一个新的节点
  4. 打印链表中的元素
  5. 双向链表尾插
  6. 双向链表尾删
  7. 双向链表头插
  8. 双向链表的头删
  9. 双链表元素查找
  10. 双向链表在pos的前面进行插入
  11. 双向链表删除pos位置的节点

双向链表的定义

//双向链表的定义
typedef int LTDatatype;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDatatype val;
}LTNode;

双向链表-创建新的节点

因为我们是动态开辟的链表，因此我们在对链表进行操作的时候，每插入一个节点时都要开辟一个节点，因此我们一样写一个接口函数来实现。
代码思路:我们只需要直接和前面单链表一样开辟思路即可，无非我们需要多管理一个prev指针，这里我们让其置为空即可。
代码实现：

LTNode* ListCreate(LTDatatype x)//创建一个新的节点
{LTNode* newnode = malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;newnode->prev = NULL;return newnode;
}

双向链表-初始化

代码思路：因为双向链表中，我们需要一个哨兵位(头节点)来管理，因此我们在初始化的时候，需要开辟一个节点作为哨兵位，然后将其的pre和next指针置为空即可。
代码实现:

LTNode* ListInit()//双链表的初始化
{LTNode* phead = ListCreate(-1);phead->next = phead;phead->prev = phead;return phead;
}

双向链表-打印链表中的元素

代码思路：由于我们是一个循环双向链表，在前面的图可以知道，我们不能够直接通过判断尾指针是否为空指针来判定是否是链表中的尾部元素，但是我们可以知道的是：链表中的最后一个节点的下一个节点，是该链表的头部，所以我们通过判定链表中当前节点的下一个节点是不是头节点，就可以知道是否是链表的尾部了。
代码实现:

void ListPrint(LTNode* pHead)//打印链表中的元素
{assert(pHead);LTNode* cur = pHead;printf("哨兵位-> ");while (pHead != cur->next){printf("%d->", cur->next->val);cur = cur->next;}printf("\n");

双向链表-尾插

代码思路:由于双向循环链表的特性，我们可以知道哨兵位的pre指向的是尾部节点，因此我们在尾插的时候不用特意的去寻找尾节点，我们只需要，用哨兵位的前驱指针找到尾部节点，让其指向新开辟的空间。因此：

  1. 通过哨兵位的前驱指针找到尾部节点
  2. 让尾部节点指向新开辟的空间。
  3. 让新开辟的空间的前驱指针指向原理的尾部节点，再让其尾指针指向头节点，即可完成双向链表的尾插。(如下图所示)
    在这里插入图片描述

函数实现：

void ListPushBack(LTNode* pHead, LTDatatype x)//双向链表尾插
{assert(pHead);LTNode* newnode = ListCreate(x);LTNode* cur = pHead->prev;//尾结点pHead->prev = newnode;newnode->next = pHead;newnode->prev = cur;cur->next = newnode;
}

函数测试:

void Test_ListPushBack()
{LTNode* sl = ListInit();ListPushBack(sl, 5);ListPushBack(sl, 2);ListPushBack(sl, 1);ListPushBack(sl, 8);ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-尾删

代码思路:这里我们依然要重复利用刚刚说到的循环双链表的性质，我们直接通过哨兵位的前驱指针来找到尾结点，来帮助我们进行尾删。

  1. 通过哨兵位前驱指针找到尾节点
  2. 找到尾结点的前驱指针，即倒数第二个节点，让其指向头节的前驱指针指向倒数第二个节点。
  3. 此时在将倒数第二个节点的尾部节点指向头节点，即可完成尾删，此时在释放掉原本的尾部节点即可。(如下图所示)
    在这里插入图片描述

代码实现:

void ListPopBack(LTNode* pHead)//双向链表尾删
{assert(pHead);assert(pHead->next);LTNode* tail = pHead->prev;//尾部节点pHead->prev = tail->prev;//让头节点指向倒数第二个节点tail->prev->next = pHead;//尾部节点指向头节点free(tail);tail = NULL;
}

函数测试:


void Test_ListPopBack()//双向链表尾删
{LTNode* sl = ListInit();ListPushBack(sl, 5);ListPushBack(sl, 2);ListPushBack(sl, 1);ListPushBack(sl, 8);printf("删除前\n");ListPrint(sl);ListPopBack(sl);printf("删除后\n");ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-头插

代码思路:

  1. 我们将哨兵位的next指针指向新开辟的节点。
  2. 将新节点的前驱指针指向原本的哨兵位
  3. 将新节点的next指向原本的第二个节点
  4. 将原本的第二个节点的前驱指针指向新节点，即可完成头插。(如下图)在这里插入图片描述

代码实现:

void ListPushFront(LTNode* pHead, LTDatatype x)//双向链表头插
{assert(pHead);LTNode* newnode = ListCreate(x);LTNode* tail = pHead->next;//记录头节点的下一个节点的位置pHead->next = newnode;//让头节点的下一个节点指向新节点newnode->prev = pHead;//让新节点的前驱指针指向头节点tail->prev = newnode;//让原本的第二个节点的前驱指针指向newnodenewnode->next = tail;//新节点的尾部节点指针原本的第二个节点
}

函数测试:

void Test_ListPushFront()//双向链表头插
{LTNode* sl = ListInit();ListPushBack(sl, 5);ListPushBack(sl, 2);ListPushBack(sl, 1);ListPushBack(sl, 8);printf("头插前\n");ListPrint(sl);printf("头插后\n");ListPushFront(sl, 10);ListPrint(sl);
}

运行结果：
在这里插入图片描述

双向链表-头删

代码思路:

  1. 我们直接通过哨兵位找到头节点，然后将哨兵位的后驱指针指向头节点的下一个节点。
  2. 将头节点的下一个节点的前驱指针指向哨兵位
  3. 在将原本的头节点释放掉即可完成头删（如下图）
    在这里插入图片描述

代码实现:

void ListPopFront(LTNode* pHead)//双向链表的头删
{assert(pHead);assert(pHead->next);LTNode* tail = pHead->next;pHead->next = tail->next;//找到第二个节点指向哨兵位后驱指针tail->next->prev = pHead;//让次节点指向哨兵位free(tail);tail = NULL;
}

函数测试:

void Test_ListPopFront()//双向链表的头删
{LTNode* sl = ListInit();ListPushBack(sl, 5);ListPushBack(sl, 2);ListPushBack(sl, 1);ListPushBack(sl, 8);printf("头删前\n");ListPrint(sl);printf("头删后\n");ListPopFront(sl);ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-元素查找

代码思路:

  1. 这里我们依然通过双向链表的性质来帮助我们判断是否走到了链表尾部。
  2. 我们定义一个cur指针去帮助我们查找
  3. 当cur碰到了尾部的时候说明查找完了，如果此时还没找到就返回空即可
  4. 在查找的过程中碰到了要查找的值直接返回此时cur的地址即可。(如下图)
    请添加图片描述

代码实现:

LTNode* ListFind(LTNode* pHead, LTDatatype x)//双链表查找
{assert(pHead);LTNode* cur = pHead->next;while (cur != pHead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}

函数测试：


void Test_ListFind()//双向链表的查找
{LTNode* sl = ListInit();ListPushBack(sl, 5);ListPushBack(sl, 2);ListPushBack(sl, 1);ListPushBack(sl, 8);printf("%p\n", ListFind(sl, 2));printf("%p\n", ListFind(sl, 999));
}

运行结果:
在这里插入图片描述

双向链表-在pos的前面进行插入

代码思路:

  1. 我们找到要插入的pos的前一个节点，让其的next指向新开辟的节点
  2. 在让此时pos前驱指针所在的位置指向新开辟的节点
  3. 再让原本插入的节点的next指向新开辟的节点
  4. 再让新开辟的节点的前驱指针和next分别指向原本pos的前一个节点和指向pos。（如下图）

在这里插入图片描述
代码实现:

void ListInsert(LTNode* pos, LTDatatype x)// 双向链表在pos的前面进行插入
{LTNode* newnode = ListCreate(x);LTNode* cur = pos->prev;//找到pos前的一个节点pos->prev = newnode;//让其前一个结点指向新结点cur->next = newnode;newnode->prev = cur;newnode->next = pos;
}

函数测试:

void Test_ListInsert()
{LTNode* sl = ListInit();ListPushBack(sl, 5);ListPushBack(sl, 2);ListPushBack(sl, 1);ListPushBack(sl, 8);printf("插入前\n");ListPrint(sl);ListInsert(ListFind(sl, 2), 99);printf("插入后\n");ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-删除pos所在的位置

代码思路:

  1. 我们找到pos所在位置的下个一个节点让其指向pos所在位置的前一个结点
  2. 此时在释放掉pos所在的位置即可完成删除

代码实现:

void ListErase(LTNode* pos)// 双向链表删除pos位置的节点
{assert(pos);LTNode* tail = pos->next;tail->prev = pos->prev;pos->prev->next = tail;free(pos);pos = NULL;
}

函数测试:

void Test_ListErase()
{LTNode* sl = ListInit();ListPushBack(sl, 5);ListPushBack(sl, 2);ListPushBack(sl, 1);ListPushBack(sl, 8);printf("删除前\n");ListPrint(sl);printf("删除后\n");ListErase(ListFind(sl, 2));ListPrint(sl);
}

运行结果:
在这里插入图片描述

双向链表-链表的销毁

关于双向链表的销毁这里就不做过多的总结了，这个和前面的打印元素有比较像，因此不懂的可以参考一下即可。
代码实现:

void ListDestory(LTNode* pHead)//双链表的销毁
{assert(pHead);LTNode* cur = pHead->next;while (pHead != cur){LTNode* tail = cur->next;free(cur);cur = tail;}free(pHead);}

总结

到这里我们可以发现，当我们写了一个插入之后会发现，那双向链表的头插和尾插，我们可以直接用我们刚刚写的插入的函数直接来实现，就完全没必要单独写尾插和头插了，至于为什么放在最后才说，是因为作者想和大家一起锻炼一下自己的思维能力，这里直接放代码就不演示了。

void ListPushBack(LTNode* pHead, LTDatatype x)//双向链表尾插
{assert(pHead);ListInsert(pHead,x);//直接再phead之前插入即可
}void ListPushFront(LTNode* pHead, LTDatatype x)//双向链表头插
{assert(pHead);ListInsert(pHead->next, x);
}

结语：今天的内容就到这里吧，谢谢各位的观看，如果有讲的不好的地方也请各位多多指出，作者每一条评论都会读的，谢谢各位。

🫵🫵🫵 这里提前祝各位新年快乐呀！ 💞

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

软件测试/测试开发丨Python 内置库 正则表达式re

软件测试/测试开发丨Python 内置库 正则表达式re

什么是正则表达式 正则表达式就是记录文本规则的代码可以查找操作符合某些复杂规则的字符串 使用场景 处理字符串处理日志 在 python 中使用正则表达式 把正则表达式作为模式字符串正则表达式可以使用原生字符串来表示原生字符串需要在字符串前方加上 rstring # 匹配字符…
阅读更多...
基于Java学生成绩管理系统设计与实现（源码+部署文档+报告）

基于Java学生成绩管理系统设计与实现（源码+部署文档+报告）

博主介绍： ✌至今服务客户已经1000、专注于Java技术领域、项目定制、技术答疑、开发工具、毕业项目实战 ✌ 🍅 文末获取源码联系 🍅 👇🏻 精彩专栏 推荐订阅 👇🏻 不然下次找不到 Java项目精品实…
阅读更多...
结构体：是第几天

结构体：是第几天

今天是该年的第几天 #include<iostream> using namespace std; struct Date //创建结构体 {int year; //年int month; //月int day; //日 }; void inputDate(Date *p) //输入函数 {cin >> p->year >> p->month >> p->day; //输入年、月、…
阅读更多...
C++内联函数与引用（超详细）

C++内联函数与引用（超详细）

文章目录 前言一、内联函数1.为什么会存在内联函数2.什么是内联函数3.内联函数注意事项 二、引用1.什么是引用2.引用的特性3.常引用4.引用使用场景5.引用与指针 总结 前言 一、内联函数 1.为什么会存在内联函数 &#x1f9d0;&#x1f9d0;首先我们介绍内联函数之前&#xf…
阅读更多...
记一次JSF异步调用引起的接口可用率降低 | 京东云技术团队

记一次JSF异步调用引起的接口可用率降低 | 京东云技术团队

前言 本文记录了由于JSF异步调用超时引起的接口可用率降低问题的排查过程&#xff0c;主要介绍了排查思路和JSF异步调用的流程&#xff0c;希望可以帮助大家了解JSF的异步调用原理以及提供一些问题排查思路。本文分析的JSF源码是基于JSF 1,7.5-HOTFIX-T6版本。 起因 问题背景…
阅读更多...
基于 Vue3 和 WebSocket 实现的简单网页聊天应用

基于 Vue3 和 WebSocket 实现的简单网页聊天应用

首先附上项目介绍,后面详细解释技术细节 1. chat-websocket 一个基于Vue3和WebSocket的简易网络聊天室项目&#xff0c;包括服务端和客户端部分。 项目地址 websocket-chat 下面是项目的主要组成部分和功能&#xff1a; 项目结构 chat-websocket/ |-- server/ # WebSocket 服…
阅读更多...
Linux上管理不同版本的 JDK

Linux上管理不同版本的 JDK

当在 Linux 上管理不同版本的 JDK 时&#xff0c;使用 yum 和 dnf 可以方便地安装和切换不同的 JDK 版本。本文将介绍如何通过这两个包管理工具安装 JDK 1.8 和 JDK 11&#xff0c;并利用软连接动态关联这些版本。 安装 JDK 1.8 和 JDK 11 使用 yum 安装 JDK 1.8 打开终端并…
阅读更多...
【AIGC表情prompt】提示词练习技巧

【AIGC表情prompt】提示词练习技巧

表情类提示词练习技巧 医疗机器人&#xff0c;男人笑脸景深&#xff0c;数据&#xff0c;座标&#xff0c;12k,c4d渲染&#xff0c;高分辨率&#xff0c;,暖色调&#xff0c;高清对比 医疗机器人&#xff0c;男人微笑&#xff0c;景深&#xff0c;数据&#xff0c;座标&#xf…
阅读更多...
线上发布稳定性方案介绍

线上发布稳定性方案介绍

目录 一、方案说明 二、线上发布问题描述 2.1 无损上下线背景说明 2.1.1 服务⽆法及时下线 2.1.2 初始化慢 2.1.3 注册太早 2.1.4 发布态与运⾏态未对⻬ 三、问题解决方案 3.1 无损下线方案 3.1.1 什么是无损下线 3.1.2 传统解决方式 3.1.3 云原生场景解决方案 3.1…
阅读更多...
提升爬虫IP时效：解决被封IP的难题

提升爬虫IP时效：解决被封IP的难题

在进行数据采集时&#xff0c;经常会遇到被目标网站封禁IP的情况&#xff0c;这给爬虫系统带来了困扰。本文将介绍如何提升爬虫IP的时效&#xff0c;解决被封IP的难题&#xff0c;帮助您顺利进行数据采集&#xff0c;不再受限于IP封禁。 第一步&#xff1a;使用爬虫IP 使用爬虫…
阅读更多...
使用element中el-cascader级联选择器实现省市区街道筛选(非动态加载)

使用element中el-cascader级联选择器实现省市区街道筛选(非动态加载)

<template><el-form ref"form" :model"form" label-width"80px"><el-form-item label"地址:" prop"addressList"><el-cascaderv-model"form.addressList":props"props":options&q…
阅读更多...
《网络是怎样连接的》2.1节图表（自用）

《网络是怎样连接的》2.1节图表（自用）

图3.1&#xff1a;协议栈的组成 图3.2&#xff1a;netstat命令查看套接字 上图中每一行就是一个套接字 图3.3&#xff1a;协议栈在浏览器访问DNS服务器与web服务器时的具体工作流程 套接字由协议栈创建 应用程序通过Socket库中的程序组件与协议栈交互
阅读更多...
飞企互联-FE企业运营管理平台 登录绕过漏洞复现

飞企互联-FE企业运营管理平台 登录绕过漏洞复现

0x01 产品简介 飞企互联-FE企业运营管理平台是一个基于云计算、智能化、大数据、物联网、移动互联网等技术支撑的云工作台。这个平台可以连接人、链接端、联通内外&#xff0c;支持企业B2B、C2B与O2O等核心需求&#xff0c;为不同行业客户的互联网转型提供支持。 0x02 漏洞概…
阅读更多...
图像拼接——基于homography的特征匹配算法

图像拼接——基于homography的特征匹配算法

目录 1. 任务要求2. 数据集3. 基于homography的特征匹配算法4. 拼接流程展示4.1 图片实例4.2 特征点位图4.3 特征点匹配结果4.4 相机校准结果4.5 拼接结果 5. 部分图像拼接结果展示 1. 任务要求 输入&#xff1a;同一个场景的两张待拼接图像&#xff08;有部分场景重合&#x…
阅读更多...
2023年03月18日_微软office365 copilot相关介绍

2023年03月18日_微软office365 copilot相关介绍

文章目录 Copilot In WordCopilot In PowerpointCopilot In ExcelCopilot In OutlookCopilot In TeamsBusiness Chat1 - copilot in word2 - copilot in excel3 - copilot in powerpoint4 - copilot in outlook5 - copilot in teams6 - business chat word 1、起草草稿 2、自动…
阅读更多...
命令模式-举例

命令模式-举例

开关和电灯之间并不存在直接耦合关系&#xff0c;在命令模式中&#xff0c;发送者与接收者之间引入了新的命令对象&#xff0c;将发送者的请求封装在命令对象中&#xff0c;再通过命令对象来调用接收者的方法。 命令模式的主要缺点如下&#xff1a; 使用命令模式可能会导致某…
阅读更多...
自然语言处理2——轻松入门情感分析 - Python实战指南

自然语言处理2——轻松入门情感分析 - Python实战指南

目录 写在开头1.了解情感分析的概念及其在实际应用中的重要性1.1 情感分析的核心概念1.1.1 情感极性1.1.2 词汇和上下文1.1.3 情感强度1.2 实际应用中的重要性 2. 使用情感分析库进行简单的情感分析2.1 TextBlob库的基本使用和优势2.1.1 安装TextBlob库2.1.2 文本情感分析示例2…
阅读更多...
二、RK3588-安装Opencv-4.8.1(C++版本)

二、RK3588-安装Opencv-4.8.1(C++版本)

1.前言 OpenCV是一个跨平台的计算机视觉和机器学习软件库&#xff0c;基于Apache2.0许可&#xff08;开源&#xff09;发行。它可以在Linux、Windows、Android和Mac OS操作系统上运行。OpenCV由一系列C函数和少量C类构成&#xff0c;同时提供了Python、Ruby、MATLAB等语言的接口…
阅读更多...
Stimulsoft BI Designer 2024.1.2 Crack

Stimulsoft BI Designer 2024.1.2 Crack

Stimulsoft BI Designer Do you want to create reports and dashboards, but you do not need to create your application? We want to offer you a great solution – Stimulsoft Designer! All you need is to connect your data, drag it onto the template page, config…
阅读更多...
Java日期和时间（一）

Java日期和时间（一）

传统的日期和时间 Date 代表的是日期和时间 构造器说明public Date&#xff08;&#xff09;创建一个Date对象&#xff0c;代表的是系统当前此刻日期时间public Date&#xff08;long time&#xff09;把时间毫秒值转换成Date日期对象 import java.util.Date;public class …
阅读更多...
最新文章

Copyright @ 2022~2023