链表之“带头双向循环链表”

目录

​编辑

1.链表的分类

2.带头双向循环链表的实现

1.创建结构体

2.创建返回链表的头节点

3.双向链表销毁

4.双向链表打印

5.双向链表尾插

6.双向链表尾删

7.双向链表头插

8.双向链表头删

9.双向链表查找

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

11.双向链表删除pos位置的节点

3.源码

 4.顺序表和链表的区别

1.链表的分类

        链表会根据是单向或者双向，带头或者不带头，循环或者非循环进行分类组合。以上情况组合起来就有8种链表结构。

其中，头指针和头节点是两个概念：

  • 头指针： 它是一个指针，指向链表中第一个节点的地址。
  • 头节点：它是一个结构体，区分数据域和指针域。数据域不存储元素，指针域则存放第一个节点的地址。
  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
  • 带头双向循环链表：带头是指链表最前面有一个头节点，它是一个结构体变量，分为数据域和指针域，数据域一般不存储数据，指针域存放的是第一个元素的地址。双向是指一个节点中有两个指针域，一个叫前驱指针，指向当前节点的前一个节点的指针，用于向前遍历；一个叫后继指针，指向当前节点的后一个节点的指针，用于向后遍历。循环是指链表最后一个节点的指针域存放的是头节点的地址，这样一来，整个链表就形成了循环的效果。

2.带头双向循环链表的实现

1.创建结构体

因为是带头双向循环链表，所以我们要定义两个指针，一个前驱指针，指向当前节点的前一个节点；还有一个后继指针，指向当前节点的后一个节点。

typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;//后继指针struct ListNode* prev;//前驱指针LTDataType val;
}LTNode;

2.创建返回链表的头节点

//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}

3.双向链表销毁

//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

4.双向链表打印

要想打印链表中的值，就得找到跳出循环的条件。因为哨兵位不存储有效的值，所以我们可以定义一个cur变量，让它指向哨兵位的下一个节点，如果cur != phead，就打印值，直到cur走到哨兵位就跳出循环。

//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("哨兵位<=>");while (cur != phead){printf("%d<=>", cur->val);cur = cur->next;}printf("\n");
}

5.双向链表尾插

带哨兵位的头节点不可能为空，哪怕链表一个值都没有，它也是指向自己的，所以要断言一下。尾插的第一步首先要找到尾，双向链表中找尾非常简单，哨兵位的前一个节点phead->prev就是尾，然后将尾节点tail的后继指针指向新节点newnode，新节点newnode的前驱指针指向tail；再将新节点newnode的后继指针指向哨兵位phead，哨兵位phead的前驱指针指向新节点newnode。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;//找尾节点LTNode* newnode = CreateLTNode(x);//phead       tail   newnodetail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

6.双向链表尾删

因为哨兵位不可能为空，所以还是得先断言一下。当链表为空时，我们不能在进行尾删，但是此时链表里边还有个哨兵位，我们得保证不能将哨兵位也删掉，所以哨兵位也得断言一下，因为链表为空时哨兵位是指向它自己的，所以断言的条件应该写成assert(phead->next != phead)。尾删时一样得先找到尾，即哨兵位得前一个节点phead->prev，因为要free掉尾，所以还得找到尾的前一个节点tailprev = tail->prev。这两个都找到后，先free掉tail，然后让tail的前一个节点tailprev的后继指针指向哨兵位phead，再让哨兵位phead的前驱指针指向tailpeev。

//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tailprev->next = phead;phead->prev = tailprev;
}

7.双向链表头插

头插时我们先搞一个新节点newnode出来，然后将newnode与哨兵位和第一个节点链接起来就可以了。但是这儿得注意一下，我们要先将newnode与第一个节点链接，然后再将哨兵位与newnode链接，如果先将哨兵位与newnode链接容易找不到第一个节点，就会很麻烦。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);//第1种方法//newnode->next = phead->next;//phead->next->prev = newnode;//phead->next = newnode;//newnode->prev = phead;//第2种方法LTNode* first = phead->next;newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

8.双向链表头删

头删时我们还得注意链表不能为空的情况，即哨兵位不能被删掉，所以还得断言assert(phead->next != phead)。只有销毁链表的时候才能将哨兵位free掉。

//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}

9.双向链表查找

查找可以配合其它函数来使用，如果找到了，就返回那个节点的地址，找不到，则返回空。

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}

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

将这个函数写完后，我们在回过头看头插、尾插，发现头插、尾插刚好可以利用这个函数以一种更简便的方式来实现。LTInsert(phead->next, x)就是头插，因为phead的下一个节点刚好就是头节点，在头节点的前面插入就是头插；LTInsert(phead, x)就是尾插，因为phead的前一个节点刚好就是尾。

//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = CreateLTNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}

11.双向链表删除pos位置的节点

这个删除操作也可以用来头删和尾删，头删就是LTErase(phead->next)，尾删就是LTErase(phead->prev)。

//删除pos的值
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);
}

3.源码

🌻List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;//后继指针struct ListNode* prev;//前驱指针LTDataType val;
}LTNode;//初始化
LTNode* LTInit();
//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x);
//打印
void LTPrint(LTNode* phead);//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos的值
void LTErase(LTNode* pos);//销毁
void LTDestory(LTNode* phead);

 🌻List.c

#include "List.h"//初始化
LTNode* LTInit()
{LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("哨兵位<=>");while (cur != phead){printf("%d<=>", cur->val);cur = cur->next;}printf("\n");
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//第1种方法LTNode* tail = phead->prev;//找尾节点LTNode* newnode = CreateLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;//第2种方法//LTInsert(phead, x);
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);//第1种写法LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tailprev->next = phead;phead->prev = tailprev;//第2种写法//LTErase(phead->prev);
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = CreateLTNode(x);//第1种方法//newnode->next = phead->next;//phead->next->prev = newnode;//phead->next = newnode;//newnode->prev = phead;//第2种方法LTNode* first = phead->next;newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev = phead;//第3种方法//LTInsert(phead->next, x);}//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);//第1种写法LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;//第2种写法//LTErase(phead->next);
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = CreateLTNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}//删除pos的值
void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);
}//销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

 4.顺序表和链表的区别

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

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

相关文章

MySQL 表的基本操作，结合项目的表自动初始化来讲

MySQL 表的基本操作，结合项目的表自动初始化来讲

有了数据库以后，我们就可以在数据库中对表进行增删改查了，这也就意味着，一名真正的 CRUD Boy 即将到来（😁）。 查表 查看当前数据库中所有的表，使用 show tables; 命令 由于当前数据库中还没有表，所以输出 Empty set。 不指定数据库 在操作表之前，可以通过 use 数…
阅读更多...
Docker容器数据卷使用

Docker容器数据卷使用

创建容器 将本地的/home/ceshi和容器的/home目录进行一个挂载,文件内容会进行同步 -v参数就是进行一个卷的挂载 主机路径:容器内的路径 [rootwq ~]# cd /home/ [rootwq home]# ll total 8 drwx------ 3 admin admin 4096 Dec 29 10:16 admin drwx------ 2 www www 4096…
阅读更多...
【洛谷 P8720】[蓝桥杯 2020 省 B2] 平面切分 题解（计算几何+集合+向量）

【洛谷 P8720】[蓝桥杯 2020 省 B2] 平面切分 题解（计算几何+集合+向量）

[蓝桥杯 2020 省 B2] 平面切分 题目描述 平面上有 N N N 条直线, 其中第 i i i 条直线是 y A i ⋅ x B i yA_{i} \cdot xB_{i} yAi​⋅xBi​ 。 请计算这些直线将平面分成了几个部分。 输入格式 第一行包含一个整数 N N N。 以下 N \mathrm{N} N 行, 每行包含两个…
阅读更多...
阿里巴巴中国站获得商品快递费用 API 返回值说明

阿里巴巴中国站获得商品快递费用 API 返回值说明

一、应用场景 阿里巴巴中国站获得商品快递费用 API&#xff08;1688.item_fee&#xff09;通常用于查询商品的快递费用。这个API的应用场景包括但不限于以下几个方面&#xff1a; 1、电商平台&#xff1a;在电商平台上&#xff0c;当用户购买商品时&#xff0c;需要知道商品的…
阅读更多...
LLM（十一）| Claude 3：Anthropic发布最新超越GPT-4大模型

LLM（十一）| Claude 3：Anthropic发布最新超越GPT-4大模型

2024年3月4日&#xff0c;Anthropic发布最新多模态大模型&#xff1a;Claude 3系列&#xff0c;共有Haiku、Sonnet和Opus三个版本。 Opus在研究生水平专家推理、基础数学、本科水平专家知识、代码等10个维度&#xff0c;超过OpenAI的GPT-4。 Haiku模型更注重效率&#xff0c;能…
阅读更多...
uniapp模仿下拉框实现文字联想功能 - uniapp输入联想（官方样式-附源码）

uniapp模仿下拉框实现文字联想功能 - uniapp输入联想（官方样式-附源码）

一、效果 废话不多说&#xff0c;上效果图&#xff1a; 在下方的&#xff1a; 在上方的&#xff1a; 二、源码 一般是个输入框&#xff0c;输入关键词&#xff0c;下拉一个搜索列表。 ElementUI有提供<el-autocomplete>&#xff0c;但uniapp官网没提供这么细&#x…
阅读更多...
15个经典面试问题及回答思路，小白以及计算机类学生的福音

15个经典面试问题及回答思路，小白以及计算机类学生的福音

前言 这几年在Java工程师招聘时&#xff0c;会看到很多人的简历都写着使用了Spring Cloud做微服务实现&#xff0c;使用Docker做自动化部署&#xff0c;并且也会把这些做为自己的亮点。而比较有趣的这其中以小公司出来的人为绝大多数&#xff0c;大的公司出来的人简历上倒是很…
阅读更多...
自动化测试基础——Pytest框架之YAML详解以及Parametrize数据驱动

自动化测试基础——Pytest框架之YAML详解以及Parametrize数据驱动

文章目录 一、YAML详解1.YAML作用2.YAML语法结构3.YAML数据类型3.1.对象3.2.数组3.3.标量 4.YAML的引用5.YAML类型转换 二、YAML的读写与清空1.YAML的读2.YAML的写3.YAML的清空 三、pytest的parametrize简单数据驱动四、pytest的parametrize结合yaml实现数据驱动五、解决pytest…
阅读更多...
rabbitmq基础（1）

rabbitmq基础（1）

1、背景 能实现消息队列的框架软件有很多&#xff0c;kafka、rabbitmq、RocketMq、activeMq、Redis&#xff08;非专业&#xff09;&#xff0c;各有各的特点和优缺点。但是之前的公司数据需求规模并非很大&#xff0c;所以采用rabbitmq作为消息队列。 2、rabbitMq的基础架构…
阅读更多...
docker单节点搭建在线商城

docker单节点搭建在线商城

本文档使用到的软件包以上传到资源中 目录 1. 创建容器并配置基础内容 1.1 将gpmall-repo上传到容器中 1.2 添加yum源 2. 安装基础服务 2.1 安装JAVA环境 2.2 安装Redis缓存服务 2.3 安装Elasticsearch服务 2.4 安装Nginx服务 2.5 安装MariaDB数据库 2.6 安…
阅读更多...
LeetCode Python - 36.有效的数独

LeetCode Python - 36.有效的数独

目录 题目答案运行结果 题目 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08…
阅读更多...
【设计模式】（二）设计模式六大设计原则

【设计模式】（二）设计模式六大设计原则

一、 设计原则概述 设计模式中主要有六大设计原则&#xff0c;简称为SOLID &#xff0c;是由于各个原则的首字母简称合并的来(两个L算一个,solid 稳定的)&#xff0c;六大设计原则分别如下&#xff1a; ​ 1、单一职责原则&#xff08;Single Responsibitity Principle&#…
阅读更多...
Fiddler入门：下载、安装、配置、抓包、customize rules

Fiddler入门：下载、安装、配置、抓包、customize rules

一、fiddler下载安装 安装包下载链接&#xff1a;https://www.telerik.com/download/fiddler 随便选个用途&#xff0c;填写邮箱&#xff0c;地区选择China&#xff0c;勾选“I accept the Fiddler End User License Agreement”&#xff0c;点击“DownLoad for windows”&…
阅读更多...
element loading遮罩层添加按钮

element loading遮罩层添加按钮

<el-table v-loading"loadingText" element-loading-text"拼命加载中" :data"tableData" :tableColumn"tableColumn" :span-method"objectSpanMethod" border :cell-style"cellStyle" :header-cell-style"…
阅读更多...
备考2024年小学生古诗文大会：历年真题15题练习和独家解析

备考2024年小学生古诗文大会：历年真题15题练习和独家解析

如何提高小学生古诗词的知识&#xff1f;如何激发小学生古诗词的学习兴趣&#xff1f;如何提高小学古诗词的学习成绩&#xff1f;如何备考2024年小学生古诗文大会&#xff1f;...如果你也在关心和这些问题&#xff0c;我的建议是参加每年一度的小学生古诗词大会&#xff08;免费…
阅读更多...
安卓类加载机制

安卓类加载机制

目录 一、ClassLoader介绍二、双亲委托机制三、类的加载过程 一、ClassLoader介绍 任何一个 Java 程序都是由一个或多个 class 文件组成&#xff0c;在程序运行时&#xff0c;需要将 class 文件加载到 JVM 中才可以使用&#xff0c;负责加载这些 class 文件的就是 Java 的类加…
阅读更多...
【深圳五兴科技】Java后端面经

【深圳五兴科技】Java后端面经

本文目录 写在前面试题总览1、java集合2、创建线程的方式3、对spring的理解4、Spring Boot 和传统 Spring 框架的一些区别5、springboot如何解决循环依赖6、对mybatis的理解7、缓存三兄弟8、接口响应慢的处理思路9、http的状态码 写在前面 关于这个专栏&#xff1a; 本专栏记录…
阅读更多...
iOS消息转发流程

iOS消息转发流程

当向Objc对象发送消息时&#xff0c;如果找到对象对应的方法&#xff0c;就会进入消息转发流程&#xff0c;给开发者提供一些最后的机会处理消息无法发送问题&#xff0c;以免出现程序崩溃。 1. 回调对象的resolveInstanceMethod方法&#xff0c;在这个方法中&#xff0c;允许开…
阅读更多...
LeetCode 热题 100 | 图论（二）

LeetCode 热题 100 | 图论（二）

目录 1 基础知识 1.1 什么是拓扑排序 1.2 如何进行拓扑排序 1.3 拓扑排序举例 2 207. 课程表 3 210. 课程表 II 菜鸟做题&#xff0c;语言是 C 1 基础知识 1.1 什么是拓扑排序 含义&#xff1a;根据节点之间的依赖关系来生成一个有序的序列。 应用&#xff1a…
阅读更多...
Mybatis实现分页查询数据（代码实操讲解）

Mybatis实现分页查询数据（代码实操讲解）

在MyBatis中实现分页查询的常见方式有两种&#xff1a;使用MyBatis内置的分页插件如PageHelper&#xff0c;或者手动编写分页的SQL语句。下面我将为你提供两种方式的示例代码。 使用PageHelper分页插件 首先&#xff0c;确保你的项目中已经添加了PageHelper的依赖。在Maven项…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发