老铺黄金等人“折A转港”
06-18
简介 数据结构是计算机存储和组织数据的方式。在工作中，我们通常会直接使用封装好的集合API，这样可以更高效地完成任务。
但作为一名程序员，掌握数据结构是非常重要的，因为它可以帮助我们更好地理解和设计算法，从而提高程序的效率和可靠性。本文将介绍几种常见的数据结构。
通过了解这些数据结构的特点和优势，可以更好地在不同场景下选择合适的数据结构。数据结构简介 常见的数据结构大致分为线性和非线性两种。
顾名思义，线性数据结构具有像直线一样的整体结构。包括数组、链表、栈、队列等。
非线性数据结构包括树、堆、图等。数组数组的结构。
数组是由多个元素组成的集合。表达式如下。
内存中存储数组的空间是连续的。每个元素都占用一定的内存空间。
这就是为什么在声明数组时必须指定长度的原因。不然不知道要占多少空间。
以Java语言为例，当声明一个数组时，数组变量会指向数组对象的起始地址，即第一个元素的位置。如下图所示，在查询数组中的某个元素时，通过 下标可以计算出该元素的内存地址。
比如要查找下标为2的元素，那么arr2的内存地址=arr的内存地址+2*元素大小。也就是说，可以通过内存地址直接访问元素。
时间很复杂。度数为 O(1)。
数组的问题然而，数组带来了一个问题：由于数组的长度是固定的，添加或删除元素都会涉及到创建一个新的数组来替换原来的数组，导致复杂度很高。例如，以下代码演示了如何向数组末尾添加元素： 代码语言：java Copy int[] arr = {1, 2, 3, 4, 5}; arr[arr.长度] = 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为例，节点的结构表达如下： 代码语言：java copy public class Node
它们可以充分利用计算机内存空间，实现灵活的动态内存管理，解决数组需要提前知道数据大小的缺点。其在内存中的存储情况如下图所示。
与数组相比，链表的插入和删除操作可以达到O(1)复杂度（只需将链尾的指针指向下一个节点或指向空），但要找到一个Node或访问一个特定编号的节点需要 O(n) 时间。单向链表 & 双向链表 上面介绍的单向链表有一个缺点：只能从头到尾遍历。
如果要删除倒数第二个节点，只能从头开始遍历。为了更灵活的操作和更高的效率，就有了双向链表。
其结构如下图所示。如果结构是双向链表，要删除倒数第二个节点，只需找到尾节点的前一个节点并将其删除即可。
Java中的LinkedList是双向链表的实现。队列和栈数组和链表主要关注数据的存储结构和访问方式，而队列和栈则关注数据的处理顺序和逻辑，各有特点。
队列的特点 队列的特点是先进先出（FIFO）：最先进入队列的元素将最先被访问或取出。也就是说，添加元素时，会在队列尾部入队，在头部出队。
。其表达式如下。
堆栈的特点如下。栈的特点是先进后出（FILO）：第一个压入栈的元素最后被访问或取出，或者最后压入栈的元素最先被访问或已删除。
取出。栈只允许在栈顶进行插入和删除操作。
一个很形象的描述是：你可以把堆栈想象成一本杂志。第一颗子弹会被压入底部，发射时会从顶部弹出。
两者的底层实现都可以根据具体需求和场景选择数组或者链表作为底层数据结构。例如Java中的ArrayBlockingQueue是通过数组实现的阻塞队列，LinkedBlockingQueue是通过队列实现的非阻塞队列。
树 树是一种非线性结构，是n个具有层次关系的有限节点的集合。树的种类也很多，比如二叉树、平衡树、2-3-4树、红黑树、B树、B+树等。
二叉树 二叉树是一种树结构，其中每个节点最多有两个子树。它通常用于实现二叉搜索树。
其特点是：左子节点的值小于根节点的值，右子节点的值大于根节点的值。以Java为例，二叉搜索树的结构表达如下： 代码语言：java copy public class Node { //当前节点的值 private int value; //父节点、左子节点、右子节点 private Node Parent,left,right;} 如下图表达。
查询时间复杂度为O(log n)。与链表相比，查询效率大大提高。
但在最坏的情况下，它可能退化为O(n)。比如下面的情况，为了避免这种情况，AVL树就诞生了。
AVL树 AVL树是一种自平衡二叉搜索树。在插入和删除操作时，它会通过左旋转或右旋转自动调整其结构，保证每个节点左右子树的高度差不超过1。
这样既保持了树的平衡，又保证了时间复杂度查询的时间复杂度为 O(log n)。以下图为例。
当节点5插入时，节点7左右子树的高度差为2，此时节点7需要进行右旋，以维持树的平衡。右旋转是指：以某个节点为旋转点，其左子节点成为其父节点，左子节点的右子节点成为其左子节点，右子节点不变。
同理，左旋转的意思是：以一个节点为旋转点，其右子节点成为其父节点，右子节点的左子节点成为其右子节点，左子节点不变。虽然AVL通过轮换来维持树的平衡，但在频繁插入和删除的场景下，频繁轮换会导致性能下降。
为了解决这个问题，红黑树被提出。红黑树 红黑树大家应该都很熟悉，但是是否理解就是另一回事了。
在面试中你应该经常被问到这个问题。红黑树也是一种自平衡二叉搜索树，它利用节点颜色来保证树的平衡。
与AVL相比，红黑树更难理解。第一个疑惑是：“不是也有左旋和右旋吗？还这么麻烦，节点颜色变了，谁混淆了？”。
我会专门写一篇文章来介绍红黑树。这里得出结论：红黑树的旋转次数比AVL树少。
因此，当插入、删除等操作较多时，通常会使用红黑树。比如大家都知道HashMap。
下图是AVL树和红黑树，其中按顺序插入9、7、6、10、5、8、4、2、1、0。可以看到两者之间存在一定的结构性差异。
二叉树的问题上面提到的树结构都是二叉树。每个节点只有两个子节点，并且它们都是有序的。
因为只有两个分支，这也是二叉树的常见问题。当数据量不断增加时，二叉树的高度会逐渐增加，导致查询效率降低。
在有磁盘I/O操作的场景中，树越高，对查询没有用处越高。为了解决上述问题，采用多树结构，可以有效降低树的高度，提高查询效率。
多树 常见的多树包括2-3-4树、B树和B+树，通常用于数据库和文件系统。他们的表述如下。
B+树是B树的扩展，更适合在磁盘或者其他存储设备上使用。 B+树中，非叶子节点不存储数据信息，只存储关键字和子节点指针。
这将存储更有效的数据，例如索引。同时，每个叶子节点都指向相邻叶子节点的指针，这样在数据库范围内的查询就变得非常高效。
堆是一种特殊的树形数据结构，其特点是：每个节点都大于或等于（小于或等于）其每个子节点。常见的堆有二叉堆、斐波那契堆等。
二叉堆是完全二叉树，可分为最大堆和最小堆。最大堆中的每个节点都大于或等于其子节点，而最小堆中的每个节点都小于或等于其子节点。
下图左边是最大堆的表示，右边不符合完全二叉树（从左到右插入的节点都是完全二叉树）。堆通常用作优先级队列，因为堆的根节点总是最大或最小。
综上所述，许多编程语言都提供了不同类型的集合类。以Java为例，我们常用的集合有List、Set、Queue、Map，它们的底层实现都是数组、链表、树等数据结构。
所以通过了解数据结构，我们可以更好地选择和使用这些集合，甚至可以自己设计更高效的数据结构来解决问题。
版权声明：本文内容由互联网用户自发贡献，本站不拥有所有权，不承担相关法律责任。如果发现本站有涉嫌抄袭的内容，欢迎发送邮件 举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。
标签：
相关文章
06-18
06-06
06-21
06-17
06-18
最新文章
【玩转GPU】ControlNet初学者生存指南
【实战】获取小程序中用户的城市信息（附源码）
包雪雪简单介绍Vue.js：开学
Go进阶：使用Gin框架简单实现服务端渲染
线程池介绍及实际案例分享
JMeter 注释 18 - JMeter 常用配置组件介绍
基于Sentry的大数据权限解决方案
【云+社区年度征文集】GPE监控介绍及使用