数据结构:链表
链表是一种常见的数据结构,它由一系列节点(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…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
【阅读笔记】MemOS: 大语言模型内存增强生成操作系统
核心速览 研究背景 研究问题:这篇文章要解决的问题是当前大型语言模型(LLMs)在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色,但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成(RA…...
OpenHarmony标准系统-HDF框架之I2C驱动开发
文章目录 引言I2C基础知识概念和特性协议,四种信号组合 I2C调试手段硬件软件 HDF框架下的I2C设备驱动案例描述驱动Dispatch驱动读写 总结 引言 I2C基础知识 概念和特性 集成电路总线,由串网12C(1C、12C、Inter-Integrated Circuit BUS)行数据线SDA和串…...
