数据结构 | 带头双向循环链表专题
数据结构 | 带头双向循环链表专题
前言
前面我们学了单链表,我们这次来看一个专题带头的双向循环链表~~
文章目录
- 数据结构 | 带头双向循环链表专题
- 前言
- 带头双向循环链表的结构
- 实现双向链表
- 头文件的定义
- 创建节点
- 哨兵位初始化
- 尾插
- 尾删
- 头插
- 头删
- 打印
- 查找
- 指定位置前插入
- 删除指定位置
- 销毁链表
- List.h
- List.c
带头双向循环链表的结构
- 注意:这里的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严
谨,但是为了同学们更好的理解就直接称为单链表的头节点。 - 带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨
的”
哨兵位
存在的意义:
- 遍历循环链表避免死循环。
- 每个节点有三部分内容:
- 保存数据的
val
- 保存下一个节点的地址next指针
- 保存前一个节点的地址prev指针
- 保存数据的
实现双向链表
我们需要实现以下功能
头文件的定义
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _val;struct ListNode* _next;struct ListNode* _prev;
}ListNode;//哨兵位初始化
ListNode* ListInit();// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType* x);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
创建节点
- malloc一个节点,然后让新节点的next和prev赋值为空,将值给了val,最后返回空间
ListNode* ListCreate(LTDataType* x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail!\n");exit(-1);}newnode->_val = x;newnode->_next = NULL;newnode->_prev = NULL;return newnode;
}
哨兵位初始化
- 这里我们初始化成
-1
代表是哨兵位,然后让前驱指针和next指针指向自己
ListNode* ListInit()
{ListNode* pHead = ListCreate(-1);pHead->_next = pHead;pHead->_prev = pHead;return pHead;
}
尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* tail = pHead->_prev;ListNode* newnode = ListCreate(x);// phead tail newnodetail->_next = newnode;newnode->_prev = tail;newnode->_next = pHead;pHead->_prev = newnode;
}
尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead->_next != pHead);ListNode* tail = pHead->_prev;ListNode* tailprev = tail->_prev;free(tail);tailprev->_next = pHead;pHead->_prev = tailprev;
}
头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->_next;ListNode* newnode = ListCreate(x);pHead->_next = newnode;newnode->_prev = pHead;newnode->_next = cur;cur->_prev = newnode;
}
头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->_next != pHead);ListNode* first = pHead->_next;ListNode* second = first->_next;pHead->_next = second;second->_prev = pHead;free(first);first = NULL;
}
打印
void ListPrint(ListNode* pHead)
{ListNode* tail = pHead->_next;printf("哨兵位->");while (tail != pHead){printf("%d->", tail->_val);tail = tail->_next;}printf("NULL\n");
}
查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){if (cur->_val == x){return cur;}cur = cur->_next;}return NULL;
}
指定位置前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = ListCreate(x);ListNode* prev = pos->_prev;prev->_next = newnode;newnode->_prev = prev;pos->_prev = newnode;newnode->_next = pos;
}
删除指定位置
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->_prev;ListNode* next = pos->_next;prev->_next = next;next->_prev = prev;free(pos);pos = NULL;
}
销毁链表
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){ListNode* next = cur->_next;free(cur);cur = next;}free(pHead);pHead = NULL;
}
List.h
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;typedef struct ListNode {LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化哨兵位
LTNode* LTInit();
//创建节点
LTNode* LTcreate(LTDataType x);
//销毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//判断是否为空
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//指定位置插入
void LTInsert(LTNode* pos, LTDataType x);
//指定位置删除
LTNode* LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
List.c
#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"//初始化哨兵位
LTNode* LTInit()
{LTNode* phead = LTcreate(-1);phead->next = phead;phead->prev = phead;return phead;
}
//创建节点
LTNode* LTcreate(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!\n");exit(-1);}newnode->next = NULL;newnode->prev = NULL;newnode->val = x;return newnode;
} //销毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<->");LTNode* cur = phead->next;while (cur != phead){printf("%d<->", cur->val);cur = cur->next;}printf("\n");
}
//判断是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->val == 0;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTcreate(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tail = NULL;tailprev->next = phead;phead->prev = tailprev;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTcreate(x);LTNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;cur->prev = newnode;newnode->next = cur;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;
}//查找
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;
}//指定位置的前面插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTcreate(x);LTNode* posprev = pos->prev;posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;}
//指定位置删除
LTNode* LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posprev = posprev;
}
- 顺序表和双向链表的分析
不同点 | 顺序表 | 链表(单链表) |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或者删除元素 | 可能需要搬移元素,效率低O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
好了,双向链表就到这里结束了,有用的话点个赞吧~~
相关文章:

数据结构 | 带头双向循环链表专题
数据结构 | 带头双向循环链表专题 前言 前面我们学了单链表,我们这次来看一个专题带头的双向循环链表~~ 文章目录 数据结构 | 带头双向循环链表专题前言带头双向循环链表的结构实现双向链表头文件的定义创建节点哨兵位初始化尾插尾删头插头删打印查找指定位置前插入…...
Redis使用Pipeline(管道)批量处理
Redis 批量处理 在开发中,有时需要对Redis 进行大批量的处理。 比如Redis批量查询多个Hash。如果是在for循环中逐个查询,那性能会很差。 这时,可以使用 Pipeline (管道)。 Pipeline (管道) Pipeline (管道) 可以一次性发送多条命令并在执…...

Linux中at命令添加一次性任务
1、工作原理 功能:在某个时间点,执行一次命令。 特点:任务是用户隔离的。 条件:必须要保证atd进程存在。 ps -ef |grep atd 原理:atd进程循环遍历队列里的任务,有任务,且到达执行时间ÿ…...

交换机基础知识之安全配置
交换机在网络基础设施中扮演着重要角色,它促进了设备之间数据包的流动。正因此,采取适当的安全措施来保护网络免受未经授权的访问和潜在攻击至关重要。本文将全面解读交换机基础安全配置知识,并提供实践方案,以保证安全的网络环境…...

Netty入门指南之Reactor模型
作者简介:☕️大家好,我是Aomsir,一个爱折腾的开发者! 个人主页:Aomsir_Spring5应用专栏,Netty应用专栏,RPC应用专栏-CSDN博客 当前专栏:Netty应用专栏_Aomsir的博客-CSDN博客 文章目录 参考文献前言单线程…...
Ubuntu20.04软件安装顺序
目录 0.网卡驱动1. sogoupinyin2. terminator3.1zsh3.2升级Cmake(有些后面的软件需要高版本Cmake)4.显卡驱动(在cuda之前)5.CUDA与cudnn,TensorRT6.OpenCV(在ROS之前)6.1先安装各种依赖6.2安装Ceres-1.14.06.3安装Pangolin6.4安装Sophus6.5安装VTK6.5编译…...

适配器模式 ( Adapter Pattern )(6)
适配器模式 ( Adapter Pattern ) 适配器模式(Adapter Pattern)是作为两个不兼容的接口之间的桥梁 适配器模式涉及到一个单一的类,该类负责加入独立的或不兼容的接口功能 举个真实的例子,读卡器是作为内存卡和笔记本之间的适配器…...

JAVA G1垃圾收集器介绍
为解决CMS算法产生空间碎片和其它一系列的问题缺陷,HotSpot提供了另外一种垃圾回收策略,G1(Garbage First)算法,通过参数-XX:UseG1GC来启用,该算法在JDK 7u4版本被正式推出,官网对此描述如下&am…...

十方影视后期“领进门”,成长与成就还得靠自身
在这个充满视觉冲击的时代,影视后期制作已经成为了一种炙手可热的艺术形式。而在这个领域,Adobe After Effects(AE)这款软件无疑是王者之一。十方影视后期作为十方教育科技旗下的艺术设计学科,不仅培养了数万名优秀的后…...
Golang之火爆原因
引言 在计算机编程领域,有很多种编程语言可供选择。然而,近年来,Golang(Go)这门相对年轻的编程语言却越来越受欢迎,备受推崇。那么,为什么Golang如此火爆?本文将探讨Golang之火爆原…...
WPF中Dispatcher对象的用途是什么
在WPF (Windows Presentation Foundation) 中,Dispatcher 对象的主要用途是提供一个与UI线程关联的消息循环系统,这允许开发者在UI线程上安排和执行任务。由于WPF的UI元素不是线程安全的,因此任何对UI元素的访问都必须从创建该元素的线程&…...

图论17-有向图的强联通分量-Kosaraju算法
文章目录 1 概念2 Kosaraju算法2.1 在图类中设计反图2.2 强连通分量的判断和普通联通分量的区别2.3 代码实现 1 概念 2 Kosaraju算法 对原图的反图进行DFS的后序遍历。 2.1 在图类中设计反图 // 重写图的构造函数public Graph(TreeSet<Integer>[] adj, boolean dire…...

ubuntu中使用 vscode 连接docker开发环境
文章目录 ubuntu中使用 vscode 连接docker开发环境步骤一:安装 Remote Development 插件步骤二:连接远程环境步骤三:开发 问题解决参考连接 ubuntu中使用 vscode 连接docker开发环境 Remote Development 是一个 Visual Studio Code 插件&…...

【广州华锐视点】海外制片人VR虚拟情景教学带来全新的学习体验
虚拟现实(Virtual Reality,简称VR)是一种利用电脑模拟产生一个三维的虚拟世界,提供用户关于视觉、听觉、触觉等感官的模拟体验的技术。随着科技的进步,VR已经被广泛应用到许多领域,包括游戏、教育、医疗、房…...
龙芯loongarch64麒麟服务器配置yum源
服务器信息: uname -a # 命令 Linux bogon 4.19.90-52.22.v2207.a.ky10.loongarch64 #1 SMP Tue Mar 14 11:18:26 CST 2023 loongarch64 loongarch64 loongarch64 GNU/Linux yum源配置: cd /etc/yum.repos.d/ vim kylin_loongarch64.repo 将下面内容拷贝…...

Centos7 单用户模式修改密码 3步搞定 666 (百分比成功)
1.第一步重新服务器 2.进入这个页面按e进入单用户模式 3.找到linux16这行 在后面添加 init/bin/bash 按ctrlx进入 4.注意是事项直接修改是报错passud: Authentication token manipulation error 需要执行权限:mount -o remount,rw /...

深度学习 机器视觉 车位识别车道线检测 - python opencv 计算机竞赛
0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 深度学习 机器视觉 车位识别车道线检测 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐! 🥇学长这里给一个题目综合评分(每项满分5分) …...

Java主流分布式解决方案多场景设计与实战
Java的主流分布式解决方案的设计和实战涉及到多个场景,包括但不限于以下几点: 分布式缓存:在Java的分布式系统中,缓存是非常重要的一部分。常用的分布式缓存技术包括Redis、EhCache等。这些缓存技术可以用来提高系统的性能和响应…...

docker安装MongoDB数据库,并且进行密码配置
很美的一首小诗> 我在外面流浪,回来时 故乡瘦了一圈—— 墩子叔走了,门前的池水 干了一半。 屋后驼背的柳树 头发散落了一地, 老房子蹲在坟边,屋顶的白云 仍在风中奔跑。 安装配置 要在Docker中安装MongoDB并启用远程连接&…...

ssh脚本找不到命令或者执行无效的解决办法
如图:今天在编写脚本时发现的这个问题, 在排除脚本语法错误、编码格式等情况下,仍然出现“bash 。。未找到命令”的字样 解决办法: 给每台虚拟机的环境变量source一下: 命令如下 source /etc/profile或者输入 vim ~…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...

密码学基础——SM4算法
博客主页:christine-rr-CSDN博客 专栏主页:密码学 📌 【今日更新】📌 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 编辑…...