数据结构:双向链表
文章目录
- 1. 双向带头循环链表的结构
- 2. 相关操作
- 2.1 创建节点
- 2.2 尾插
- 2.3 头插
- 2.4 打印
- 2.5 尾删
- 2.6 头删
- 2.7 查找
- 2.8 指定位置前/后插入
- 2.9 删除指定位置的节点
- 2.10 删除指定位置后的节点
- 2.11 销毁链表
- 3.顺序表与链表区别

1. 双向带头循环链表的结构

与单链表不同的是:
- 双向链表有一个“哨兵位”作为单独的头节点
- 每个节点都可以指向其前驱和后继节点
- 链表是循环的
带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”
“哨兵位”存在的意义:遍历循环链表避免死循环。
typedef int ListDataType;
typedef struct List
{ListDataType data;struct List* prev;//指向前驱节点struct List* next;//指向后继节点
}List;
2. 相关操作
2.1 创建节点

- 创建的每个节点应该自己成环
List* BuyNode(ListDataType x)
{List* newnode = (List*)malloc(sizeof(List));if (newnode == NULL){perror(malloc);return NULL;}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;
}
创建哨兵位:
int main()
{//哨兵位List* head = BuyNode(-1);return 0;
}
2.2 尾插

void ListPushBack(List* phead, ListDataType x)
{assert(phead);List* newnode = BuyNode(x);newnode->next = phead;newnode->prev = phead->prev;//尾节点指向新节点phead->prev->next = newnode;phead->prev = newnode;
}
2.3 头插

void ListPushFront(List* phead, ListDataType x)
{assert(phead);List* newnode = BuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next = newnode;//只有头节点时,就是头节点的prevphead->next->prev = newnode;
}
2.4 打印
由于是循环链表,所以循环停止的条件应该是:cur != head
void ListPrint(List* phead)
{assert(phead);List* cur = phead->next;while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

2.5 尾删
- 不能没有节点
- 尾节点的前驱节点指向头节点
- 头节点指向尾节点的前驱节点
- 释放尾节点
void ListPopBack(List* phead)
{assert(phead);//只有头节点assert(phead->next != phead);List* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);
}
2.6 头删
- 不能没有节点
- 待删除节点的后继节点的prev指向头节点
- 头节点指向待删除节点的后继节点
void ListPopFront(List* phead)
{assert(phead);assert(phead->next != phead);List* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);
}
2.7 查找
List* ListFind(List* phead, ListDataType x)
{assert(phead);assert(phead->next != phead);List* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
2.8 指定位置前/后插入
- 将新节点与指定位置相连即可
指定位置前
void ListPosFrontInsert(List* pos, ListDataType x)
{assert(pos);List* newnode = BuyNode(x);List* prev = pos->prev;newnode->prev = prev;newnode->next = pos;prev->next = newnode;pos->prev = newnode;
}
指定位置后
void ListPosBackInsert(List* pos, ListDataType x)
{assert(pos);List* newnode = BuyNode(x);List* next = pos->next;newnode->next = next;newnode->prev = pos;next->prev = newnode;pos->next = newnode;
}
2.9 删除指定位置的节点
- 将指定位置的前驱节点、后继节点连接即可
void ListPosDel(List* pos)
{assert(pos);List* prev = pos->prev;List* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}
2.10 删除指定位置后的节点
- 若指定位置是尾节点,则应该执行头删
void ListPosAfterDel(List* phead, List* pos)
{assert(phead);assert(pos);if (pos->next == phead){ListPopFront(phead);}else{List* del = pos->next;del->next->prev = pos;pos->next = del->next;free(del);}
}
2.11 销毁链表
- 此接口的参数是一级指针,所以并不能将哨兵位销毁;因此需要再调用处再将哨兵位置为空
void ListDestroy(List* phead)
{assert(phead);assert(phead->next != phead);List* cur = phead->next;while (cur != phead){List* next = cur->next;free(cur);cur = next;}cur = NULL;free(phead);phead = NULL;
}

3.顺序表与链表区别
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间上 | 物理上一定连续 | 逻辑上连续,物理上不一定连续 |
| 随机访问 | O(1) | O(N) |
| 任意位置插入或删除 | 可能需要搬运元素,效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表,空间不够需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储,频繁访问 | 任意位置频繁插入/删除 |
| 缓存利用率 | 高 | 低 |
相关文章:
数据结构:双向链表
文章目录 1. 双向带头循环链表的结构2. 相关操作2.1 创建节点2.2 尾插2.3 头插2.4 打印2.5 尾删2.6 头删2.7 查找2.8 指定位置前/后插入2.9 删除指定位置的节点2.10 删除指定位置后的节点2.11 销毁链表 3.顺序表与链表区别 1. 双向带头循环链表的结构 与单链表不同的是…...
51单片机之数码管显示表白数字篇
朝菌不知晦朔 蟪蛄不知春秋 眼界决定境界 CSDN 请求进入专栏 是否进入《51单片机专栏》? 确定 目录 数码管的简介 数码管引脚定义 数码管的原理图 74HC245 代码实现 静态数码管的显示 动态数码管的显示 数码管实现表白画面 数码管的简介 L…...
代码随想录算法训练营DAY16 | 二叉树 (3)
一、LeetCode 104 二叉树的最大深度 题目链接:104.二叉树的最大深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/ 思路:采用后序遍历递归求解。 class Solution {int ans 0;public int maxDepth(TreeNode root) {if(root null){retur…...
springboot(ssm大学生计算机基础网络教学系统 在线课程系统Java系统
springboot(ssm大学生计算机基础网络教学系统 在线课程系统Java系统 开发语言:Java 框架:springboot(可改ssm) vue JDK版本:JDK1.8(或11) 服务器:tomcat 数据库:mys…...
前端架构: 脚手架的开发流程和常用框架
脚手架的开发流程 脚手架的创建 $ npm init 脚手架的开发 分包 分包是指当我们一个脚手架比较复杂的时候,不可能把所有的js代码全部写在一个脚手架当中势必会把它建很多的不同的模块 package,通常我们会把它称之为一个分包的过程会和实际的这个项目一样…...
3.0 Hadoop 概念
本章着重介绍 Hadoop 中的概念和组成部分,属于理论章节。如果你比较着急可以跳过。但作者不建议跳过,因为它与后面的章节息息相关。 Hadoop 整体设计 Hadoop 框架是用于计算机集群大数据处理的框架,所以它必须是一个可以部署在多台计算机上…...
mysql 对于null字段排序处理
最近遇到一个需求 ,需要对一个报表的多个字段进行多字段复杂条件排序 排序字段为NULL时 Mysql对于排序字段为NULL时,有自身默认的排序规则,默认是认为null 值 是无穷小 ELECT id,script_id,last_modified,live_count,next_show FROM virtua…...
NLP_语言模型的雏形 N-Gram 模型
文章目录 N-Gram 模型1.将给定的文本分割成连续的N个词的组合(N-Gram)2.统计每个N-Gram在文本中出现的次数,也就是词频3.为了得到一个词在给定上下文中出现的概率,我们可以利用条件概率公式计算。具体来讲,就是计算给定前N-1个词时࿰…...
mac电脑flutter环境配置,解决疑难问题
准备工作 首先搭建flutter的环境需要使用到flutter的sdk,可以直接跳去官网下载:Choose your first type of app - Flutter 中文文档 - Flutter 中文开发者网站 - Flutter,下载时要注意你电脑所使用的芯片是Intel的还是苹果的芯片。 下载好的…...
C++ bool 布尔类型
在C 中 bool类型占用1个字节长度,bool 类型只有两个取值,true 和 false,true 表示“真”,false 表示“假”。 需要注意的C中使用cout 打印的时候是没有true 和 false 的 只有0和1 ,这里0表示假,非0表示真 …...
DC-7靶机渗透详细流程
信息收集: 1.存活扫描: 由于靶机和kali都是nat的网卡,都在一个网段,我们用arp-scan会快一点: arp-scan arp-scan -I eth0 -l └─# arp-scan -I eth0 -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:dd:ee:6…...
提速MySQL:数据库性能加速策略全解析
提速MySQL:数据库性能加速策略全解析 引言理解MySQL性能指标监控和评估性能指标索引优化技巧索引优化实战案例 查询优化实战查询优化案例分析 存储引擎优化InnoDB vs MyISAM选择和优化存储引擎存储引擎优化实例 配置调整与系统优化配置调整系统优化优化实例 实战案例…...
Flink实战六_直播礼物统计
接上文:Flink实战五_状态机制 1、需求背景 现在网络直播平台非常火爆,在斗鱼这样的网络直播间,经常可以看到这样的总榜排名,体现了主播的人气值。 人气值计算规则:用户发送1条弹幕互动,赠送1个荧光棒免费…...
Compose | UI组件(十五) | Scaffold - 脚手架
文章目录 前言一、Scaffold脚手架简介二、Scaffold的主要组件三、如何使用Scaffold四、Compose中Scaffold脚手架的具体例子例子1:基本Scaffold布局例子2:带有Drawer的Scaffold布局例子3:带有Snackbar的Scaffold布局 总结 前言 Compose中的Sca…...
Vue-60、Vue技术router-link的replace属性
1、作用:控制路由跳转时操作浏览器历史记录的模式 2、浏览器的历史记录有两种写入方式:分别是push和replace,push是追加历史记录,replace是替换当前记录。路由跳转时候默认为push 3、如何开启replace模式: <router-link rep…...
Hive与Presto中的列转行区别
Hive与Presto列转行的区别 1、背景描述2、Hive/Spark列转行3、Presto列转行 1、背景描述 在处理数据时,我们经常会遇到一个字段存储多个值,这时需要把一行数据转换为多行数据,形成标准的结构化数据 例如,将下面的两列数据并列转换…...
探讨CSDN等级制度:博客等级、原力等级、创作者等级
个人名片: 🦁作者简介:学生 🐯个人主页:妄北y 🐧个人QQ:2061314755 🐻个人邮箱:2061314755qq.com 🦉个人WeChat:Vir2021GKBS 🐼本文由…...
2.8作业
sqlite3数据库操作接口详细整理,以及常用的数据库语句 头文件: #include <sqlite3.h> 编译时候要加上-lsqlite3 gcc a.c -lsqlite3 1)sqlite3_open 打开一个数据库,如果数据库不存在,则创建一个数据库 2&am…...
机器学习中常用的性能度量—— ROC 和 AUC
什么是泛化能力? 通常我们用泛化能力来评判一个模型的好坏,通俗的说,泛化能力是指一个机器学期算法对新样本(即模型没有见过的样本)的举一反三的能力,也就是学以致用的能力。 举个例子,高三的…...
微服务入门篇:Nacos注册中心(Nacos安装,快速入门,多级存储,负载均衡,环境隔离,配置管理,热更新,集群搭建,nginx反向代理)
目录 1.Nacos安装1.官网下载2.解压到本地3.启动nacos 2.Nacos快速入门1.在父工程中导入nacos依赖2.给子项目添加客户端依赖3.修改对应服务的配置文件4.启动服务,查看nacos发现情况 3.Nacos服务多级存储模型4.NacosRule负载均衡5. 服务实例的权重设置6.环境隔离&…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
js 设置3秒后执行
如何在JavaScript中延迟3秒执行操作 在JavaScript中,要设置一个操作在指定延迟后(例如3秒)执行,可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法,它接受两个参数: 要执行的函数&…...
Linux 内存管理调试分析:ftrace、perf、crash 的系统化使用
Linux 内存管理调试分析:ftrace、perf、crash 的系统化使用 Linux 内核内存管理是构成整个内核性能和系统稳定性的基础,但这一子系统结构复杂,常常有设置失败、性能展示不良、OOM 杀进程等问题。要分析这些问题,需要一套工具化、…...
