当前位置: 首页 > news >正文

常见的数据结构及应用

文章目录

  • 前言
  • 数据结构介绍
    • 数组
    • 链表
    • 队列和栈
  • 总结

前言

数据结构是计算机存储、组织数据的方式。在工作中,我们通常会直接使用已经封装好的集合API,这样可以更高效地完成任务。但是作为一名程序员,掌握数据结构是非常重要的,因为它可以帮助我们更好地理解和设计算法,从而提高程序的效率和可靠性。本文将对常见的几种数据结构进行介绍,通过了解这些数据结构的特点和优势,可以更好地在不同场景下选择合适的数据结构。

数据结构介绍

常见的数据结构大体分为两种类型:线性和非线性。

线性数据结构见名思义,整体结构的图像是一条直线。包括数组、链表、栈、队列等。
非线性数据结构包括,树、堆、图等。

数组

数组是由多个元素组成的一个集合,表现形式如下图

在这里插入图片描述

在内存中存储数组的空间是连续的,每个元素占据一定的内存空间,这也是为什么在声明数组时要指定长度,不然不知道要占用多少空间。以 Java 语言为例,当声明一个数组后,数组变量会指向数组对象的起始地址,也就是第一个元素的位置,如下图

在这里插入图片描述

以此看来,当查询数组中的某个元素时,通过下标就可以计算出这个元素的内存地址,比如想查找下标为2的元素,那么arr[2]的内存地址 = arr的内存地址 + 2 * 元素大小,也就可以直接通过内存地址访问元素,时间复杂度为O(1)。

但是,数组也会带来一个问题:由于数组长度是固定的,所以在添加或删除元素时会涉及到创建新的数组来替换原数组,导致复杂度较高。例如,下面的代码演示了如何在数组末尾添加一个元素:

int[] arr = {1, 2, 3, 4, 5};  arr[arr.length] = 6; // 将要添加的元素放到数组的最后一个位置  int[] newArr = new int[arr.length + 1]; // 创建一个新的数组,长度加1  for (int i = 0; i < newArr.length; i++) {  newArr[i] = arr[i]; // 将原数组中的元素复制到新数组中  
}  arr = newArr; // 使用新数组替换原数组

示例代码在内存中的活动如下图

在这里插入图片描述

在 Java 中有很多集合的底层实现都是基于数组,例如大家常用的 ArrayList、Vector、HashMap、ArrayBlockingQueue等等。

链表

链表由一系列结点组成,每个节点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个节点地址的指针域。以 Java 为例,一个节点的结构是这样表示的:

public class Node<T> {//存储数据元素的数据域private T value;//下一个节点地址的指针域private Node next;
}

每个元素的指针指向下一个元素,从而形成链表,表现形式如下图。

在这里插入图片描述

与数组不同,链表在内存中是非连续的空间,可以充分利用计算机内存空间,实现灵活的内存动态管理,解决了数组需要预先知道数据大小的缺点。其在内存中的存储如下图

在这里插入图片描述

相比于数组,链表的插入和删除操作可以达到O(1)的复杂度(只需要将链尾的指针指向下个节点或者指向null即可),但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。

上面介绍的是单向链表,单向链表有个缺点:只能只能从头到尾遍历。如果要删除倒数第二个节点,只能从头遍历。为了更加灵活的操作和更高的效率,就有了双向链表,其结构表示如下图

在这里插入图片描述

如果结构为双向链表,要删除倒数第二个节点,只用找到尾节点的前面一个节点并删除即可。Java 中的 LinkedList 就是一个双向链表的实现。

队列和栈

数组和链表的关注点主要聚焦于数据的存储结构和访问方式,而队列和栈关注的则是数据的处理顺序和逻辑,有自己的特点。

队列的特点是先进先出(FIFO):第一个进入队列的元素会第一个被访问或取出,或者说在添加元素时在队尾排队依次入队,在队头依次出队。其表现形式如下图

在这里插入图片描述

栈的特点是先进后出(FILO):第一个入栈的元素最后一个被访问或被取出,或者说最后一个入栈的元素会第一个被访问或被取出。栈只允许在栈顶进行插入和删除操作。

有一个很形象的描述就是:可以将栈想象成一个弹夹,最先装入的子弹会被压入底部,而射出时则是从顶部弹出。

在这里插入图片描述

两者的底层实现可以根据具体需求和场景选择数组或链表作为底层数据结构。例如 Java 中的 ArrayBlockingQueue 是通过数组实现的阻塞队列,LinkedBlockingQueue 通过队列实现的非阻塞队列。

树是一种非线性结构,是由n个有限节点组成一个具有层次关系的集合。树也有很多类型,比如二叉树、平衡树、2-3-4树、红黑树、B树、B+树。

二叉树是每个节点最多有两个子树的树结构,通常用于实现二叉查找树,其特点为:左子节点的值小于根节点的值,右子节点的值大于根节点的值。以 Java 为例,一个二叉查找树的结构是这样表示的:

public class Node {//当前节点的值private int value;//父节点、左子节点、右子节点private Node parent,left,right;}

表现形式如下图

在这里插入图片描述

其查询的时间复杂度为O(log n),相对于链表,查询效率大大提升。但是在最坏情况下可能会退化成O(n),比如下面这种情况

在这里插入图片描述


为了避免这种情况,诞生了AVL树。AVL树是一种自平衡的二叉查找树,在进行插入和删除操作时,会通过左旋或者右旋自动调整自身的结构,确保每个节点的左右子树的高度差不超过1,从而保持树的平衡,也保障了查询的时间复杂度为O(log n)。

以下图为例,当插入节点5时,节点7左右子树的高度差为2,这时候节点7就需要进行右旋保持树的平衡。

在这里插入图片描述
右旋就是:以某个节点为旋转点,其左子节点变为其父节点,左子节点的右子节点变为其左子节点,右子节点不变。
同理,左旋就是:以某个节点为旋转点,其右子节点变为其父节点,右子节点的左子节点变为其右子节点,左子节点不变。


虽然AVL通过旋转保持树的平衡,但是在插入和删除频繁的场景中,频繁的旋转会导致性能下降,为解决此问题红黑树被提出。

红黑树大家应该都比较耳熟,面试的时候应该经常会被问到,但是理不理解是另一回事。

红黑树也是自平衡的二叉查找树,它是通过节点颜色来保证树的平衡的。相对AVL,红黑树较难被理解,第一疑惑就是:“不也是左旋右旋吗?还这么麻烦,节点颜色变来变去,迷惑谁呢?”。

红黑树后面专门写一篇文章介绍,这里先给结论:红黑树的旋转次数相对于AVL树来说较少,因此在插入、删除等操作较多的情况下,通常使用红黑树,比如大家都知道的HashMap。下图显示的是按顺序插入9, 7, 6, 10, 5, 8, 4, 2, 1, 0的AVL树和红黑树,可以看到两者在结构上存在一定的差异。

在这里插入图片描述


上面说的几种树都是二叉树,即每个节点只有两个分支,并且都都是有序的。因为只有两个分支,所以这也是二叉树的通病,当数据越来越多的时候,树的高度也会越高,这种情况就不适合数据库和文件系统这种场景了。

上面提到的几种树结构都是二叉树,每个节点只有两个子节点,并且都是有序的。当数据量不断增加时,二叉树的高度也会逐渐增加,从而导致查询效率降低,并且在有磁盘I/O操作的场景下,树越高越不利于查询。

为了解决上述问题,采用多叉树结构,可以有效地降低树的高度,提高查询效率。

常见的多叉树有2-3-4树、B树和B+树,通常在数据库和文件系统中会使用到,其表现形式如下图。

在这里插入图片描述

B+树是B树的一种扩展,它更适合用于磁盘或其他存储设备中。在B+树中,非叶子节点不保存数据信息,只保存关键字和子节点指针,这样会存储更多有效数据,比如索引。同时,每个叶子节点都指向相邻叶子节点的指针,这样的话在数据库范围查询会变得非常高效。

堆是一种特殊的树形数据结构,其特点为:每个节点都大于或等于(小于或等于)其每个子节点。

常见的堆有二叉堆、斐波那契堆等,二叉堆是一种完全二叉树,可以分为最大堆和最小堆,最大堆中的每个节点都大于或等于其子节点,最小堆中的每个节点都小于或等于其子节点。下图左为最大堆的表示,右不符合为一个完全二叉树(依次从左到右插入的节点为完全二叉树)。

在这里插入图片描述

堆通常被用作优先队列,因为堆的根节点总是最大的或最小的。

总结

很多编程语言都提供了不同类型的集合类,以 Java 为例,我们常用的集合有List、Set、Queue、Map,其底层的实现就是数组、链表或树这几种数据结构。所以通过了解数据结构,我们可以更好地选择和使用这些集合,甚至可以自行设计更高效的数据结构来解决问题。

相关文章:

常见的数据结构及应用

文章目录 前言数据结构介绍数组链表队列和栈树堆 总结 前言 数据结构是计算机存储、组织数据的方式。在工作中&#xff0c;我们通常会直接使用已经封装好的集合API&#xff0c;这样可以更高效地完成任务。但是作为一名程序员&#xff0c;掌握数据结构是非常重要的&#xff0c;…...

基于模型预测人工势场的船舶运动规划方法,考虑复杂遭遇场景下的COLREG(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【UE5 Cesium】19-Cesium for Unreal 建立飞行跟踪器(4)

遗留问题 在上一篇博客中&#xff08;【UE5 Cesium】18-Cesium for Unreal 建立飞行跟踪器&#xff08;3&#xff09;&#xff09;&#xff0c;我们实现了飞机变速飞行的功能&#xff0c;但是还存在两个问题&#xff0c;分别是&#xff1a; &#xff08;1&#xff09;由于UE的…...

TrustZone

TrustZone技术 让我们从最重要的问题开始&#xff1a;为什么存在TrustZone技术&#xff0c;它防御什么&#xff1f;保护用 C 和 C 编写的大型程序免受黑客攻击可能是一个挑战。内存损坏漏洞是一个常见问题&#xff0c;尽管消除它们是安全工程师的核心目标&#xff0c;但从操作…...

✔ ★【备战实习(面经+项目+算法)】 10.16学习时间表(总计学习时间:5h)

✔ ★【备战实习&#xff08;面经项目算法&#xff09;】 坚持完成每天必做如何找到好工作1. 科学的学习方法&#xff08;专注&#xff01;效率&#xff01;记忆&#xff01;心流&#xff01;&#xff09;2. 每天认真完成必做项&#xff0c;踏实学习技术 认真完成每天必做&…...

React + Router

React Router 这个只是专门讲解 React Router 新开的例子。 教程来源&#xff1a;https://reactrouter.com/en/main/start/tutorial 创建新项目 yarn create vite my-react-router-app --template react-ts cd my-react-router-app yarn安装 React Router 依赖: yarn add…...

微信小程序设置动态变量设值

微信小程序设置动态变量设值 微信小程序如何动态变量设值&#xff1f; 示例代码如下&#xff1a; setValFunc() {const key this.data.currentPickerid; // 业务需求动态键值key&#xff0c;或者是上一界面获取的动态key值const value 变量值;this.setData({[${key}]: valu…...

闪站侠洗衣洗鞋多门店多用户管理系统,洗鞋店干洗店小程序开发;

闪站侠洗护软件是多分店多用户管理系统&#xff0c;一个分店可以同时关联多个用户。闪站侠洗护管理软件通过互联网为洗衣店/洗鞋店干洗店提供加盟或直营连锁管理&#xff1b; 实现会员洗衣的门店收衣->上门收衣->开单拍照->清洗护理/工厂洗涤->微&#xff5c;信/短…...

JDBC增删改查示例

数据库表 CREATE TABLE customers ( id int NOT NULL AUTO_INCREMENT, name varchar(15) DEFAULT NULL, email varchar(20) DEFAULT NULL, birth date DEFAULT NULL, photo mediumblob, PRIMARY KEY (id) ) ENGINEInnoDB AUTO_INCREMENT39 DEFAULT CHARSETgb2312;…...

emqx broker安装

emqx broker安装 Emq x百万级开源 MQTT 消息服务器 是基于 Erlang/OTP 语言平台开发 一款完全开源&#xff0c;高可用低时延的百万级分布式物联网 MQTT 5.0 消息服务器 官方地址: https://www.emqx.com/zh Centos7 安装 #下载Centos7 amd64位版本 wget https://www.emqx.c…...

如何选择国产压力测试工具?

随着互联网的飞速发展&#xff0c;软件应用的性能和稳定性变得愈发重要。无论是在线购物网站、社交媒体平台还是移动应用程序&#xff0c;用户都期望能够快速、流畅地访问和使用它们。为了确保应用程序在高负载下仍能够正常运行&#xff0c;压力测试工具变得至关重要。在国内&a…...

基于AT89C51流水花样灯proteus仿真设计

一、仿真原理图&#xff1a; 二、仿真效果图&#xff1a; 三、仿真工程&#xff1a; c51单片机流水灯花样灯proteus仿真设计资源-CSDN文库...

android U广播详解(二)

android U广播详解&#xff08;一&#xff09; 基础代码介绍 广播相关 // 用作单个进程批量分发receivers&#xff0c;已被丢弃 frameworks/base/services/core/java/com/android/server/am/BroadcastReceiverBatch.java // 主要逻辑所在类&#xff0c;包括入队、分发、结束…...

导航守卫的使用记录和beforeEach( )死循环的问题

前置导航守卫beforeEach的使用 import Vue from vue import VueRouter from vue-router // 进度条 import NProgress from nprogress import nprogress/nprogress.cssVue.use(VueRouter)// 路由表 const routes [{path: "/",redirect: "/home",},{path: …...

SpringMVC源码分析(三)HandlerExceptionResolver启动和异常处理源码分析

问题&#xff1a;异常处理器在SpringMVC中是如何进行初始化以及使用的&#xff1f; Spring MVC提供处理异常的方式主要分为两种&#xff1a; 1、实现HandlerExceptionResolver方式&#xff08;HandlerExceptionResolver是一个接口&#xff0c;在SpringMVC有一些默认的实现也可以…...

系统架构与Tomcat的安装和配置

2023.10.16 今天是学习javaweb的第一天&#xff0c;主要学习了系统架构的相关知识和原理&#xff0c;下载了web服务器软件&#xff1a;Tomcat&#xff0c;并对其进行了配置。 系统架构 包括&#xff1a;C/S架构 和 B/S架构。 C/S架构&#xff1a; Client / Server&#xff0…...

【Shell脚本】根据起止日期获取Alert日志内容

【Shell脚本】根据起止日期获取Alert日志内容 根据输入的起止日期字符串&#xff0c;检索Oracle告警日志&#xff0c;打印中间的日志行内容。 #!/bin/bash # $1 START_TIME_STR, e.g. "Oct 17 07:" # $2 END_TIME_STR, e.g. "Oct 17 08:" source /home/o…...

Library projects cannot set applicationId. applicationId is set to

Library projects cannot set applicationId. applicationId is set to com.xxx.library_cache in default config. 删掉即可...

【兔子王赠书第2期】《案例学Python(基础篇)》

文章目录 前言推荐图书本书特色本书目录本书样章本书读者对象粉丝福利丨评论免费赠书尾声 前言 随着人工智能和大数据的蓬勃发展&#xff0c;Python将会得到越来越多开发者的喜爱和应用。身边有很多朋友都开始使用Python语言进行开发。正是因为Python是一门如此受欢迎的编程语…...

用户行为数据案例

一、环境要求 HadoopHiveSparkHBase 开发环境。 二、数据描述 本数据集包含了2017-09-11至2017-12-03之间有行为的约5458位随机用户的所有行为&#xff08;行为包括点击、购买、加购、喜欢&#xff09;。数据集的每一行表示一条用户行为&#xff0c;由用户ID、商品ID、商品类…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...