数据结构——双向循环链表
目录
前言
一、链表的分类
二、双向循环链表
2.1 开辟新的节点
2.2 链表初始化
2.3 打印链表
2.4 链表的尾插
2.5 链表的头插
2.6 链表的尾删
2.7 链表的头删
2.8 查找链表
2.9 在pos位置之后插入数据
2.10 删除pos位置的数据
三、完整代码实现
四、顺序表和双向链表的优缺点分析
总结
前言
我们之前讲了顺序表和单链表,它们但是线性表的一种,今天我们来讲链表中的双向循环链表。
一、链表的分类


二、双向循环链表
我们之前讲了单链表,今天我们来实现双向带头循环链表。
接口实现:
//list.h//链表初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//打印链表
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 LTErase(LTNode* pos);//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);void LTDesTroy(LTNode* phead);
在实现代码前,我们要先用结构体来定义链表的类型。由于是循环链表,所以我们需要两个指针,分别指向节点的前驱节点和后继节点。
typedef int LTDataType;
//双向循环链表结构体类型
typedef struct ListNode {LTDataType data;struct ListNode* prev;//前驱节点struct ListNode* next;//后继节点
}LTNode;
2.1 开辟新的节点
在初始化之前,我们来实现开辟新的节点
//新的节点
LTNode* LTBuyNode(LTDataType x) {//为新的节点开辟空间LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;//让新节点头尾相连newNode->next = newNode->prev = newNode;return newNode;
}
2.2 链表初始化
链表的初始化我们可以有两种写法:
//写法一 传入头节点的地址
void LTInit(LTNode** pphead) {assert(pphead);//哨兵位*pphead = LTBuyNode(-1);
}
//写法二 返回哨兵位,不传入值
LTNode* LTInit() {LTNode* pphead = LTBuyNode(-1);return pphead;
}
我们给哨兵位的值赋为-1(任意都可以,哨兵位不作为有效数据)。
我们更推荐使用第二种方法,因为保持接口的一致性。
2.3 打印链表
如果我们往链表中插入数据,可以通过打印知道是否插入成功
void LTPrint(LTNode* phead) {assert(phead);//从哨兵位下一个节点开始打印LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
其中要注意的是循环开始是从哨兵位下一个节点开始的,结束条件是pcur走到哨兵位,即遍历了整个链表。
2.4 链表的尾插
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);//要插入的新的节点LTNode* newNode = LTBuyNode(x);//phead phead->prev newNodenewNode->next = phead;newNode->prev = phead->prev;phead->prev->next = newNode;phead->prev = newNode;
}
尾插入一个节点,我们要改变的是哨兵位,哨兵位的前驱节点(即尾节点),新节点三个节点的指向
2.5 链表的头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);//插入的新节点LTNode* newNode = LTBuyNode(x);//phead phead->next newNodenewNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}
头插入一个节点,我们要改变的是哨兵位,哨兵位的后继节点(即第一个有效数据节点),新节点三个节点的指向
2.6 链表的尾删
void LTPopBack(LTNode* phead) {assert(phead);//链表不为空assert(phead->next != phead);//phead phead->prev->prev(prev) phead->prev(del)LTNode* prev = phead->prev->prev;LTNode* del = phead->prev;phead->prev = prev;prev->next = phead;free(del);del = NULL;
}
尾部删除一个节点,我们要改变的是删除元素的前驱节点,哨兵位的指向,最后释放删除节点
2.7 链表的头删
void LTPopFront(LTNode* phead) {assert(phead);//链表不为空assert(phead->next != phead);//phead phead->next(del) phead->next->next(next)LTNode* del = phead->next;LTNode* next = phead->next->next;phead->next = next;next->prev = phead;free(del);del = NULL;
}
头部删除一个节点,我们要改变的是哨兵位,删除节点的后继节点,最后释放删除节点
2.8 查找链表
如果我们要指定位置插入或者删除,我们就要找到这个位置,我们进行链表的查找
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}
如果存在返回当前节点,不存在返回空。
2.9 在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newNode = LTBuyNode(x);//newNode pos pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}
我们要改变新节点,pos节点,pos节点的后继节点的指向。
注意:我们要先把pos的后继节点的前驱节点指向新节点,才能把pos的后继节点指向新节点,不然反过来会找不到pos节点后继节点的位置。
2.10 删除pos位置的数据
//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
我们要改变新节点,pos节点的前驱,pos节点的后继节点的指向。
2.11 销毁链表
因为每个节点都是单独开辟的空间,所以我们要依次销毁。
//方法一
void LTDesTroy(LTNode** pphead) {assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}
//方法二
void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur =next;}free(phead);phead = NULL;
}
与链表的初始化一样,我们有两种方法,但是我们一般选择第二种方法,为了保持接口的一致性,但是第二种方法我们要在函数外面手动给链表置为空。
三、完整代码实现
list.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//双向循环链表结构体类型
typedef struct ListNode {LTDataType data;struct ListNode* prev;//前驱节点struct ListNode* next;//后继节点
}LTNode;//链表初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//打印链表
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 LTErase(LTNode* pos);//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);void LTDesTroy(LTNode* phead);
list.c
#include"list.h"//新的节点
LTNode* LTBuyNode(LTDataType x) {//为新的节点开辟空间LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;//让新节点头尾相连newNode->next = newNode->prev = newNode;return newNode;
}//链表初始化
//写法一 传入头节点的地址
//void LTInit(LTNode** pphead) {
// assert(pphead);
// 哨兵位
// *pphead = LTBuyNode(-1);
//}
//写法二 返回哨兵位,不传入值
LTNode* LTInit() {LTNode* pphead = LTBuyNode(-1);return pphead;
}//打印链表
void LTPrint(LTNode* phead) {assert(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 newNodenewNode->next = phead;newNode->prev = phead->prev;phead->prev->next = newNode;phead->prev = newNode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newNode = LTBuyNode(x);//phead phead->next newNodenewNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}//尾删
void LTPopBack(LTNode* phead) {assert(phead);assert(phead->next != phead);//phead phead->prev->prev(prev) phead->prev(del)LTNode* prev = phead->prev->prev;LTNode* del = phead->prev;phead->prev = prev;prev->next = phead;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead) {assert(phead);assert(phead->next != phead);//phead phead->next(del) phead->next->next(next)LTNode* del = phead->next;LTNode* next = phead->next->next;phead->next = next;next->prev = phead;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);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);//newNode pos pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁链表
/*void LTDesTroy(LTNode** pphead) {assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}*/
void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur =next;}free(phead);phead = NULL;
}
listest.c
#include"list.h"void Listest() {//LTNode* plist = NULL;//LTInit(&plist);LTNode* plist=LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);//1 2 3 4;LTPrint(plist);//头插/*LTPushFront(plist, 8);LTPushFront(plist, 7);LTPushFront(plist, 6);LTPushFront(plist, 5);LTPrint(plist);*///尾删/* LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);//删除失败,链表为空//LTPopBack(plist);*///头删/*LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);//删除错误链表为空//LTPopFront(plist);*///查找LTNode* retFInd = LTFind(plist,1);/*if (retFInd) {printf("找到了\n");}else {printf("没找到\n");}*///在pos后面插入数据/*LTInsert(retFInd, 50);LTPrint(plist);*///删除pos位置上的数据/*LTErase(retFInd);LTPrint(plist);*///销毁链表//LTDesTroy(&plist);//保持接口一致性LTDesTroy(plist);plist = NULL;
}int main() {Listest();return 0;
}
四、顺序表和双向链表的优缺点分析
不同点 | 顺序表 | 链表(单链表) |
---|---|---|
存储空间上 | 物理上⼀定连续 | 逻辑上连续,但物理上不⼀定连续 |
随机访问 | ⽀持O(1) | 不⽀持:O(N) |
任意位置插⼊或删除元素 | 可能需要搬移元素,效率低O(N) | 只需修改指针指向 |
插⼊ | 动态顺序表,空间不够时需要扩 容 | 没有容量的概念 |
应⽤场景 | 元素⾼效存储+频繁访问 | 任意位置插⼊和删除频繁 |
总结
上述文章我们讲了链表的双向带头循环链表的实现,希望对你有所帮助
相关文章:

数据结构——双向循环链表
目录 前言 一、链表的分类 二、双向循环链表 2.1 开辟新的节点 2.2 链表初始化 2.3 打印链表 2.4 链表的尾插 2.5 链表的头插 2.6 链表的尾删 2.7 链表的头删 2.8 查找链表 2.9 在pos位置之后插入数据 2.10 删除pos位置的数据 三、完整代码实现 四、顺序表和双向…...
使用ZLMediaKit搭建服务器实现推流拉流
源码:https://gitee.com/xia-chu/ZLMediaKit?utm_sourcealading&utm_campaignrepo 文档:https://docs.zlmediakit.com/zh/tutorial/ 检查gcc版本gcc -v检查cmake是否安装cmake --version安装gitsudo apt-get install git按照文档进行克隆 # 国内用…...

【拦截器Interceptor】springboot拦截器的使用和原理
【拦截器Interceptor】springboot拦截器的使用和原理 【一】拦截器简介(1)简介【2】作用 【二】实现步骤【1】自定义拦截器,实现拦截器接口HandlerInterceptor【2】将拦截器添加到容器当中【3】配置拦截器的拦截规则【4】拦截器的执行顺序 【…...
Android12 user版本无法进入recovery问题
1.前言 之前Android9的时候公司自己写了一个简单的OTA在线升级,调用Recovery升级系统。后来Android12的时候想使用AB升级,发现我这套代码AB升级完成了之后,重启却无法切到B,所以造成升级一直是失败的。后来想着要不还是把AB关掉直…...
Android沙盒机制
Android沙盒机制 Android Q文件存储机制修改成了沙盒模式,应用只能访问自己沙盒下的文件和公共媒体文件 存储(也就是write)私有目录和公共媒体文件都不需要WRITE_EXTERNAL_STORAGE权限读取(也就是read)私有目录不需要…...
【C++】每日一题 290 单词规律
给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律。 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。 #include <string> #include <unordered_ma…...
CSS3 animation-direction 属性
CSS3 animation-direction 属性 定义和用法 animation-direction 属性定义是否循环交替反向播放动画。 **注意:**如果动画被设置为只播放一次,该属性将不起作用。 默认值:normal继承:否可动画化:否。请参阅 可动画…...
【mysql 5.7 没有ini 文件,手动添加配置文件】
在安装目录的根目录添加my.ini配置文件: 注意注释的内容, 其中server-id 在开启日志归档的时候,一定要配置, [mysql] # 设置mysql客户端默认字符集 default-character-setutf8[mysqld] #server id 一定要设置,否则无法…...
【Python】从零开始学习Python中的随机模块:实现验证码生成功能
欢迎来CILMY23的博客 本篇主题为 从零开始学习Python中的随机模块:实现验证码生成功能 个人主页:CILMY23-CSDN博客 个人专栏系列: Python | C语言 | 数据结构与算法 | C 感谢观看,支持的可以给个一键三连,点赞关注…...
游戏动画技术:从传统到深度学习
一、传统游戏动画技术简介 3D游戏动画的骨骼动画和蒙皮技术动画交互控制:状态机、动作融合和IK基于状态机的动画控制原理和问题 二、Motion Matching技术简介 传统状态机动画的缺陷Motion Matching的原理:根据角色状态自动匹配动画Dance Card动捕流程…...

Github 2024-04-12 开源项目日报 Top10
根据Github Trendings的统计,今日(2024-04-12统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目6TypeScript项目2Cuda项目1C++项目1C项目1HTML项目1Jupyter Notebook项目1JavaScript项目1Python - 100天从新手到大师 创建周期:22…...
若依下整合多个Redis
提前总结,因此项目已多处使用Redis1 故此我创建的Redis工厂只添加了Redis2并不影响Redis1。但如若还有Redis3、4、5可按照下述方法继续往Redis工厂里添加 下述代码添加到 RedisConfig import org.springframework.beans.factory.annotation.Autowired; import org…...
SRTP + RTCP + SCTP
SRTP(Secure Real-time Transport Protocol) 主要功能:SRTP 是 RTP 的一个扩展,提供额外的安全特性,如加密、完整性校验和认证。它旨在保护实时传输的音频和视频流不被窃听或篡改。加密传输:SRTP 使用强加密…...

每日一题 — 串联所有单词的子串
30. 串联所有单词的子串 - 力扣(LeetCode) 思路:因为words里面的每一个字符串的长度都是固定的,所以可以将题转换成字符在字符串中的所有异位词 设出哈希表定义left和right进窗口维护count判断出窗口维护count 代码: …...

Android studio顶部‘app‘红叉- Moudle ‘XX.app’ dosen’t exist in project
Android studio顶部app红叉- Moudle ‘XX.app’ dosen’t exist in project 1、现象: 运行老项目或者有时候替换项目中的部分代码,明明没有错但是Android studio就编译报错了。 1.1 Android studio顶部app红叉。 1.2 点击Build没有clear菜单࿰…...

软考证书有用吗?软考证书的含金量大吗?
一、以考代评 通过考试并获得相应级别计算机专业技术资格(水平)证书的人员,表明其已具备从事相应专业岗位工作的水平和能力,用人单位可根据《工程技术人员职务试行条例》有关规定和工作需要,从获得计算机专业技术资格…...
自动化测试原理,怎么理解?【UI自动化】
首先,UI自动化是一种通过自动化工具或框架模拟用户与用户界面交互的测试技术。在软件开发过程中,这种技术对于确保用户界面的正确性和稳定性起着至关重要的作用。 具体来说,UI自动化的原理主要基于以下三个核心环节: 界面定位&am…...
typedef,#define,asserr,exit函数,free函数
一.typedef的应用 1.给已定的变量类型起个别名 加不加typedef,类型不变 (加之前是个数组,加之后是数组类型; 加之前是个函数指针,加之后是函数指针类型;) struct _person {char name[20];in…...

Linux的重要命令(二)+了解Linux目录结构
目录 一.Linux的目录结构 二.查看文件内容命令 1.cat 命令 2.more 命令 3.less 命令 4.head 命令 5.tail 命令 6.拓展 head 和 tail 的其他用法 编辑 三.统计文件内容的命令-wc 编辑 四.检索和过滤文件内容的命令-grep 编辑 编辑 五.压缩命令 gzip 和 bz…...
nmap使用
常用语句 主机发现和端口扫描 主机发现 sudo nmap -sn 192.168.80.0/24或sudo arp-scan -larp-scan是Kali Linux自带的一款ARP扫描工具。轻量级扫描工具,用来扫描局域网的主机还是挺好用的,由于扫描的少,所以扫描速度比较快,可…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001
qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类,直接把源文件拖进VS的项目里,然后VS卡住十秒,然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分,导致编译的时候找不到了。因…...
大模型真的像人一样“思考”和“理解”吗?
Yann LeCun 新研究的核心探讨:大语言模型(LLM)的“理解”和“思考”方式与人类认知的根本差异。 核心问题:大模型真的像人一样“思考”和“理解”吗? 人类的思考方式: 你的大脑是个超级整理师。面对海量信…...

npm安装electron下载太慢,导致报错
npm安装electron下载太慢,导致报错 背景 想学习electron框架做个桌面应用,卡在了安装依赖(无语了)。。。一开始以为node版本或者npm版本太低问题,调整版本后还是报错。偶尔执行install命令后,可以开始下载…...