常见的数据结构及应用

文章目录

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

前言

数据结构是计算机存储、组织数据的方式。在工作中,我们通常会直接使用已经封装好的集合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,其底层的实现就是数组、链表或树这几种数据结构。所以通过了解数据结构,我们可以更好地选择和使用这些集合,甚至可以自行设计更高效的数据结构来解决问题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/161388.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL——六、库表操作(下篇)

MySQL 一、INSERT语句二、REPLACE语句三、UPDATE语句四、delete和TRUNCATE语句五、MySQL用户授权1、密码策略2、用户授权和撤销授权 一、INSERT语句 #在表里面插入数据&#xff1a;默认情况下&#xff0c;一次插入操作只插入一行 方式1&#xff1a; INSERT [INTO] 表名 [(colu…

新一代开源语音库CoQui TTS冲到了GitHub 20.5k Star

Coqui TTS 项目介绍 Coqui 文本转语音&#xff08;Text-to-Speech&#xff0c;TTS&#xff09;是新一代基于深度学习的低资源零样本文本转语音模型&#xff0c;具有合成多种语言语音的能力。该模型能够利用共同学习技术&#xff0c;从各语言的训练资料集转换知识&#xff0c;来…

vue2 解密图片地址(url)-使用blob文件-打开png格式图片

一、背景 开发中需要对加密文件进行解码&#xff0c;如图片等静态资源。 根据后端给到的url地址&#xff0c;返回的是图片文件&#xff0c;但是乱码的&#xff0c;需要解码成png图片进行展示 二、请求接口 将后端返回的文件转为文件流&#xff0c;创建Blob对象来存储二进制…

设计模式:工厂方法模式(C#、JAVA、JavaScript、C++、Python、Go、PHP):

本节主要介绍设计模式中的工厂方法模式。 简介&#xff1a; 工厂方法模式&#xff0c;它是对简单工厂模式的进一步抽象化&#xff0c;其好处是可以使系统在不修改原来代码的情况下引进新的产品&#xff0c;即满足开闭原则。 它定义了一个用于创建对象的工厂接口&#xff0c;让…

游游的字母串 (环形数组两点之间的位置)

题目链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 题目&#xff1a; 样例&#xff1a; 输入 yab 输出 3 思路&#xff1a; 暴力枚举&#xff0c;全部变成对应的26个字母字符需要的操作步数&#xff0c;取最少的一个操作步数&#xff0c; 这里的操作步数&#xff0…

laravel中锁以及事务的简单使用

一、首先来说一下什么是共享锁&#xff1f;什么是排他锁&#xff1f; 共享&#xff1a;我可以读 写 加锁 , 别人可以 读 加锁。 排他&#xff1a;只有我 才 可以 读 写 加锁 , 也就是说&#xff0c;必须要等我提交事务&#xff0c;其他的才可以操作。 二、简单例子实现加锁 锁…

tomcat 服务器

tomcat 服务器 tomcat: 是一个开源的web应用服务器。区别nginx&#xff0c;nginx主要处理静态页面&#xff0c;那么动态请求&#xff08;连接数据库&#xff0c;动态页面&#xff09;并不是nginx的长处&#xff0c;动态的请求会交给tomcat进行处理。 nginx-----转发动态请求-…

PCL 坡度滤波算法地面分割(C++详细过程版)

目录 一、算法原理1、实现流程2、参考文献二、代码实现三、结果展示一、算法原理 1、实现流程 1、格网示意图 2、计算格网行列数 公式中的特殊符号为向上取整,

Cesium Vue(三)— 相机配置

1. 坐标系转换 1.1 cesium使用到的坐标系 屏幕坐标系&#xff0c;二维的笛卡尔坐标系&#xff0c;API > Cartesian2地理空间坐标系&#xff0c;WGS-84坐标系&#xff0c; API > Cartographic(经度&#xff0c;维度&#xff0c;高度)三维笛卡尔空间直角坐标系&#xff0…

GPT4 Advanced data analysis Code Interpreter 做行业数据分析、可视化处理图像、视频、音频等

1. 跨境电商如何用ChatGPT选品 ChatGPT Jungle scout 案例&#xff1a;跨境电商如何用ChatGFT选品 ChatGPTJungle scout 素材和资料来自&#xff1a; Jungle ScoutEM, Michael Soltis 和 文韬武韬AIGC 1.1 从Jungle scout上下载数据 Date Range > Last 90 days Downlo…

python+大数据校园卡数据分析 计算机竞赛

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 基于yolov5的深度学习车牌识别系统实现 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;4分工作量&#xff1a;4分创新点&#xff1a;3分 该项目较为新颖&am…

Stable Diffusion绘画,卡通,教室

1 girl, parted lips, blush, makeup, light smile, school uniform, classroom, light rays, glow, thighs, collarbone, narrow waist, (masterpiece), wallpaper 1个女孩&#xff0c;双唇&#xff0c;腮红&#xff0c;化妆&#xff0c;浅笑&#xff0c;校服&#xff0c;教室…

基于SSM框架的安全教育平台

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…

【Eclipse】设置自动提示

前言&#xff1a; eclipse默认有个快捷键&#xff1a;alt /就可以弹出自动提示&#xff0c;但是这样也太麻烦啦&#xff01;每次都需要手动按这个快捷键&#xff0c;下面给大家介绍的是&#xff1a;如何设置敲的过程中就会出现自动提示的教程&#xff01; 先按路线找到需要的页…

uniapp使用uQRCode绘制二维码,下载到本地,调起微信扫一扫二维码核销

1.效果 2.在utils文件夹下创建uqrcode.js // uqrcode.js //--------------------------------------------------------------------- // github https://github.com/Sansnn/uQRCode //---------------------------------------------------------------------let uQRCode {…

设计模式(1)-设计模式前置基础知识

1&#xff0c;设计模式概述 1.1 软件设计模式的产生背景 "设计模式"最初并不是出现在软件设计中&#xff0c;而是被用于建筑领域的设计中。 1977年美国著名建筑大师、加利福尼亚大学伯克利分校环境结构中心主任克里斯托夫亚历山大&#xff08;Christopher Alexand…

PS 学习笔记

书籍&#xff1a;Photoshop 2022从入门到精通-敬伟-微信读书 1. PS 常用快捷键 复位右侧基本工作栏&#xff1a;【窗口】-【工作区】- 【复位基本功能】 Ctrl 鼠标滚轮&#xff1a;主界面图片左右滚动Shift 鼠标滚轮&#xff1a;主界面图片上下滚动Alt 鼠标滚轮&#xff1…

算法通关村第19关【青铜】| 动态规划

动态规划&#xff08;Dynamic Programming&#xff0c;简称DP&#xff09;是一种解决多阶段决策过程最优化问题的数学方法。它通常用于解决那些具有重叠子问题和最优子结构性质的问题&#xff0c;这些问题可以分解为多个相互关联的子问题。 动态规划的核心思想是将原问题分解为…

模板学堂|DataEase协助电商企业开展用户运营

DataEase开源数据可视化分析平台于2022年6月正式发布模板市场&#xff08;https://dataease.io/templates/&#xff09;。模板市场旨在为DataEase用户提供专业、美观、拿来即用的仪表板模板&#xff0c;方便用户根据自身的业务需求和使用场景选择对应的仪表板模板&#xff0c;并…

MyBatis进行单表多表查询以及其中的${}涉及的SQL注入

目录 回顾&#xff1a; 参数占位符#{}和${} ${}唯一使用地方 使用${}造成的SQL注入漏洞 like查询 mapper中接收结果的参数 resultType和resultMap​编辑 多表查询 回顾&#xff1a; 参数占位符#{}和${} #{} 占位符语法通常用于模板引擎或动态查询语句中。它是一种更加安全的…