数据结构:链表
链表是一种常见的数据结构,它由一系列节点(Node)组成,每个节点包含两个部分:数据域和指针域。数据域用于存储数据元素的值,而指针域则用于指向链表中的下一个节点。这种结构使得链表能够动态地进行插入和删除操作,具有较高的灵活性。
链表的主要特点包括:
-
动态分配:链表的大小可以在运行时动态地增长或缩小,不需要预先分配固定大小的空间。
-
插入和删除效率高:在已知某一节点位置的情况下,链表的插入和删除操作可以在常数时间内完成,无需像数组那样移动大量元素。
-
元素访问顺序性:链表中的元素是顺序访问的,从头节点开始,依次访问到尾节点。这种顺序性使得链表在处理需要按序处理的数据时非常有用。
链表的类型主要有以下几种:
-
单向链表:每个节点只有一个指针,指向下一个节点。单向链表只能从头节点开始,顺序访问到尾节点。
-
双向链表:每个节点有两个指针,一个指向前一个节点,另一个指向后一个节点。双向链表可以从任意节点开始,向前或向后访问其他节点。
-
循环链表:在单向链表或双向链表的基础上,尾节点的指针指向头节点,形成一个环状结构。循环链表可以从任意节点开始,遍历整个链表。
在实际应用中,链表被广泛用于实现各种数据结构和算法,如栈、队列、哈希表等。同时,由于链表在插入和删除操作上的高效性,它也常被用于需要频繁进行这些操作的场景,如文本编辑器中的撤销/重做功能、操作系统的任务调度等。
然而,链表也有一些缺点,如需要额外的空间来存储指针、不能直接访问特定位置的元素(需要从头节点开始遍历)等。因此,在选择使用链表还是其他数据结构时,需要根据具体的应用场景和需求进行权衡。
1. 单向链表(Singly Linked List)
单向链表中的每个节点包含数据和指向下一个节点的指针。链表的头指针指向第一个节点,最后一个节点的指针指向NULL,表示链表的结束。
示例代码:
#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表末尾插入节点
void append(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}// 打印链表
void printList(struct Node* head) {struct Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}int main() {struct Node* head = NULL;append(&head, 10);append(&head, 20);append(&head, 30);printList(head);return 0;
}
输出:
10 -> 20 -> 30 -> NULL
2. 双向链表(Doubly Linked List)
双向链表中的每个节点包含数据、指向下一个节点的指针和指向前一个节点的指针。这样可以方便地从任意节点向前或向后遍历链表。
示例代码:
#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构
struct Node {int data;struct Node* prev;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;
}// 在链表末尾插入节点
void append(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;
}// 打印链表
void printList(struct Node* head) {struct Node* temp = head;while (temp != NULL) {printf("%d <-> ", temp->data);temp = temp->next;}printf("NULL\n");
}int main() {struct Node* head = NULL;append(&head, 10);append(&head, 20);append(&head, 30);printList(head);return 0;
}
输出:
10 <-> 20 <-> 30 <-> NULL
3. 循环链表(Circular Linked List)
循环链表可以是单向的也可以是双向的。在循环链表中,最后一个节点的指针指向链表的头节点,形成一个环。
示例代码:
#include <stdio.h>
#include <stdlib.h>// 定义循环链表节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在循环链表末尾插入节点
void append(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;newNode->next = *head; // 指向自身形成环return;}struct Node* temp = *head;while (temp->next != *head) {temp = temp->next;}temp->next = newNode;newNode->next = *head; // 新节点指向头节点
}// 打印循环链表
void printList(struct Node* head) {if (head == NULL) return;struct Node* temp = head;do {printf("%d -> ", temp->data);temp = temp->next;} while (temp != head);printf("(回到起点)\n");
}int main() {struct Node* head = NULL;append(&head, 10);append(&head, 20);append(&head, 30);printList(head);return 0;
}
输出:
10 -> 20 -> 30 -> (回到起点)
链表结构在不同的应用场景中都有其独特的优势,选择合适的链表类型可以提高程序的效率和可读性。
相关文章:
数据结构:链表
链表是一种常见的数据结构,它由一系列节点(Node)组成,每个节点包含两个部分:数据域和指针域。数据域用于存储数据元素的值,而指针域则用于指向链表中的下一个节点。这种结构使得链表能够动态地进行插入和删…...
领克Z20结合AI技术,革新自动驾驶辅助系统
眼瞅着,再有不到 5 个星期,春节就要热热闹闹地登场啦!对于在外辛苦打拼了一整年的打工人而言,回家过年可不就是这一年里心心念念、最最期盼的高光时刻嘛。这不,这几天各地的高速公路愈发熙熙攘攘起来,川流不…...
vector快慢指针+例题详解
1.快慢指针 例题 给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从…...
重温设计模式--1、组合模式
文章目录 1 、组合模式(Composite Pattern)概述2. 组合模式的结构3. C 代码示例4. C示例代码25 .应用场景 1 、组合模式(Composite Pattern)概述 定义:组合模式是一种结构型设计模式,它允许你将对象组合成…...
单片机:实现SYN6288语音播报(附带源码)
单片机实现SYN6288语音播报 SYN6288是一款广泛应用于语音合成的IC,可以通过串口与单片机(如51系列、STM32等)进行通信,实现场景化的语音播报。通过连接外部存储设备(如SD卡)存储语音文件或直接通过内部语音…...
cookie,session,token 的区别
解决什么问题?Cookie(客户端存储)问题来了 Session(会话)解决的问题问题来了 token(令牌)解决的问题问题:token是无状态的如何解决? 解决什么问题? 解决http无状态的问题,说简单点就是用户身份的验证 举个例子: 张三在银行里…...
基于OpenAI Whisper AI模型自动生成视频字幕:全面解析与实战指南
在数字化时代,视频内容已成为信息传播的重要载体。然而,为视频添加字幕却是一项繁琐且耗时的工作。幸运的是,随着人工智能技术的飞速发展,特别是OpenAI Whisper模型的推出,我们有了更加高效、智能的解决方案。 一、Op…...
物理学天空的两朵乌云——量子论与相对论
物理学天空的两朵乌云——量子论与相对论 爱因斯坦的青春与科学的辉煌起点 提到爱因斯坦,我们往往会联想到一个经典的形象——乱糟糟的头发,叼着烟斗,脸上满是岁月的皱纹。然而,这张深入人心的照片并不是他科学创造力的象征。实…...
聚类之轮廓系数
Silhouette Score(轮廓系数)是用于评估聚类质量的指标之一。它衡量了数据点与同簇内其他点的相似度以及与最近簇的相似度之间的对比。 公式 对于一个数据点 i: a(i): 数据点 i 到同簇内其他点的平均距离(簇内不相似度ÿ…...
Jenkins 构建流水线
在 Linux 系统上安装 Jenkins 服务,以及配置自动化构建项目 前置准备环境:docker、docker-compose、jdk、maven 一、环境搭建 1. Jenkins 安装 (1)拉取镜像 # 安装镜像包,默认安装最新版本 docker pull jenkins/jen…...
RTK部分模糊度固定测量流程图
部分模糊度剔除常用测量: 周跳或失锁时间优先剔除;按俯仰角剔除;按浮点模糊度协方差大小剔除模糊度;按信号强度剔除卫星;...
力扣-数据结构-2【算法学习day.73】
前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?建议灵神的题单和代码随想录)和记录自己的学习过程,我的解析也不会做的非常详细,只会提供思路和一些关…...
操作系统导论读书笔记
目录 虚拟化抽象:进程抽象:进程概念 虚拟化 抽象:进程 本章讨论操作系统提供的基本的抽象—— 进程。进程的非正式定义非常简单:进程就是运行中的程序。程序本身是没有生命周期的,它只是存在磁盘上面的一些指令&…...
基于3D-Speaker进行区分说话人项目搭建过程报错记录 | 通话录音说话人区分以及语音识别 | 声纹识别以及语音识别 | pyannote-audio
0. 研究背景 在外呼系统中,我们的后台管理系统通常要对电话录音的内容进行提取和分析。那么说到分析,我们就要对录音中的两个人的对话进行分离,然后分别分析,比如分析客户是否有合作的意愿,分析客服讲的话术是否合理&…...
如何使用流式渲染技术提升用户体验
提示:记录工作中遇到的需求及解决办法 文章目录 什么是流式渲染?Node.js 实现简单流式渲染声明式 Shadow DOM,不依赖 javascript 实现react 实现流式渲染总结提示:以下是本篇文章正文内容,下面案例可供参考 什么是流式渲染? 流式渲染主要思想是将HTML文档分块(chunk)…...
【接口自动化连载】使用yaml配置文件自动生成接口case
直接上干货撸代码,有一些是通用的工具类代码,一次性封装永久使用,期待大家的关注,一起加油!!! 配置文件 根据不同的业务需求进行配置,例如Goods服务、Order服务分开配置࿰…...
前端安全 常见的攻击类型及防御措施
1. 跨站脚本攻击(XSS) 描述:跨站脚本(XSS:Cross-Site Scripting)是一种安全漏洞,允许攻击者向网站注入恶意客户端代码。该代码由受害者执行从而让攻击者绕过访问控制并冒充用户。XSS攻击可以分…...
来道面试题——CopyOnWriteArrayList
原理 初始化时候,CopyOnWriteArrayList内部维护了一个可变数组,用于存储元素当执行数据变更操作的时候,会先创建一个原数组的副本,在副本上进行写操作,修改副本中的元素。写操作完成之后,把原数组的引用指…...
【Rust自学】5.1. 定义并实例化struct
喜欢的话别忘了点赞、收藏加关注哦,对接下来的教程有兴趣的可以关注专栏。谢谢喵!(・ω・) 5.1.1. 什么是struct struct的中文意思为结构体,它是一种自定义的数据类型,它允许程序为相关联的值命名和打包&am…...
React 生命周期完整指南
React 生命周期完整指南 1. 生命周期概述 1.1 React 16.3 之前的生命周期 初始化阶段 constructorcomponentWillMountrendercomponentDidMount 更新阶段 componentWillReceivePropsshouldComponentUpdatecomponentWillUpdaterendercomponentDidUpdate 卸载阶段 componentWil…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
