数据结构：八大数据结构分类

﹏ヽ暗。殇╰゛Y 2023-09-28 14:16 155阅读 0赞

## 数据结构分类 ##

> 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。  
> 常用的数据结构有：`数组`，`栈`，`链表`，`队列`，`树`，`图`，`堆`，`散列表(哈希表) 等`，如图所示：

![在这里插入图片描述][b413519f0e7c495290c5e5d792048e0b.png]  
每一种数据结构都有着独特的数据存储方式，下面为大家介绍它们的结构和优缺点。

## 1、数组 ##

> 数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为1。

int[] data = new int[100]；data[0]  = 1;

![800abd9020114475a052e005ddbe1255.png][]

**优点：**  
1、按照索引查询元素速度快  
2、按照索引遍历数组方便

**缺点：**  
1、数组的大小固定后就无法扩容了  
2、数组只能存储一种类型的数据  
3、添加，删除的操作慢，因为要移动其他的元素。

**适用场景：**  
频繁查询，对存储空间要求不大，很少增加和删除的情况。

## 2、队列 ##

> 队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，

**示例图如下：**  
![在这里插入图片描述][797eb3074b1b472c85a254740a7f3f54.png] ![!\[在这里插入图片描述\]][2226405eb517490bb658768624e6bfaa.png]

注意 : `栈是先进后出，队列是先进先出——两者虽然都是线性表，但原则是不同的，结构不一样嘛。`

**使用场景** ：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

## 3、链表 ##

> 链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域  
> (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

![在这里插入图片描述][a112efee01d9441d9c435548ba92df15.png]

Java 的 LinkedList 类可以很形象地通过代码的形式来表示一个链表的结构：  
![在这里插入图片描述][c151f19c38864819b68b3ccc9b1b7fde.png]

这是一种双向链表，当前元素 item 既有 prev 又有 next，不过 first 的 prev 为 null，last 的 next 为 null。如果是单向链表的话，就只有 next，没有 prev。  
![在这里插入图片描述][9849dc3f7bec4d189bfc81205767499b.png]  
单向链表的缺点是只能从头到尾依次遍历，而双向链表可进可退，既能找到下一个，也能找到上一个——每个节点上都需要多分配一个存储空间。

链表中的数据按照“链式”的结构存储，因此可以达到内存上非连续的效果，数组必须是一块连续的内存。  
![在这里插入图片描述][3e99f12cc3034e28bae0eb19037899d3.png]

由于不必按照顺序的方式存储，链表在插入、删除的时候可以达到 O(1) 的时间复杂度（只需要重新指向引用即可，不需要像数组那样移动其他元素）。除此之外，链表还克服了数组必须预先知道数据大小的缺点，从而可以实现灵活的内存动态管理。

**链表的优点：**  
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；  
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

**缺点：**  
因为含有大量的指针域，占用空间较大；  
查找元素需要遍历链表来查找，非常耗时。

**适用场景：**  
数据量较小，需要频繁增加，删除操作的场景

## 4、栈 ##

> 栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。

栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。

![在这里插入图片描述][2575ef2c045640a383ea3ae182b7b706.png]

栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。

## 5、树 ##

> 树是一种典型的非线性结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

**它具有以下的特点：**

1.  每个节点有零个或多个子节点；
2.  没有父节点的节点称为根节点；
3.  每一个非根节点有且只有一个父节点；
4.  除了根节点外，每个子节点可以分为多个不相交的子树；

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。  
![在这里插入图片描述][8feb7bd8bafa4c9fa4913534facf588e.png]

***二叉树是树的特殊一种，具有如下特点：***

1.  每个结点最多有两颗子树，结点的度最大为2。
2.  左子树和右子树是有顺序的，次序不能颠倒。
3.  即使某结点只有一个子树，也要区分左右子树。

`二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。`

**下图展示了树的一些术语：**  
![在这里插入图片描述][312872b095e9478892fbdf07f4336b69.png]

**扩展：**  
二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。

## 6、图 ##

> 图是一种复杂的非线性结构，由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。

![在这里插入图片描述][7bcd20f4716f4180ac081f40a6eab08d.png]  
上图共有 V0，V1，V2，V3 这 4 个顶点，4 个顶点之间共有 5 条边。

在线性结构中，数据元素之间满足唯一的线性关系，每个数据元素（除第一个和最后一个外）均有唯一的“前驱”和“后继”；

在树形结构中，数据元素之间有着明显的层次关系，并且每个数据元素只与上一层中的一个元素（父节点）及下一层的多个元素（子节点）相关；

而在图形结构中，节点之间的关系是任意的，图中任意两个数据元素之间都有可能相关。

图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。

## 7、散列表(哈希表) ##

> 散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

记录的存储位置=f(key) 这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，

**其示例图如下：**  
![在这里插入图片描述][a16177a443f0452a8797b2c2715a5c9c.png]  
![在这里插入图片描述][25fd536c3cc74e91a952043389e765a0.png]

从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。  
数组的最大特点就是查找容易，插入和删除困难；而链表正好相反，查找困难，而插入和删除容易。  
哈希表很完美地结合了两者的优点， Java 的 HashMap 在此基础上还加入了树的优点。

## 8、堆 ##

> 堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象

**具有以下的性质：**

*  堆中某个节点的值总是不大于或不小于其父节点的值；
 *  堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆的定义如下：n个元素的序列\{k1,k2,ki,…,kn\}当且仅当满足下关系时，称之为堆。  
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，

**示例图如下：**

![在这里插入图片描述][1b4db6a672ed4ce391cef85942e2dc9a.png]

因为堆有序的特点，一般用来做数组中的排序，称为堆排序。

## 关联算法文章： ##

> 这里有一些相关的文章，可以参考一下

1、[斐波那契数列的迭代算法和递归算法][Link 1]  
2、[埃氏筛法(埃氏算法)][Link 2]  
3、[BF算法（暴⼒算法）-- 模式匹配算法][BF_--]  
4、[数据结构：八大数据结构分类][Link 3]  
5、[JAVA中 常用七大排序算法][JAVA_]  
6、[Linked 链表反转 - 迭代 与 递归][Linked _ - _ _]

[b413519f0e7c495290c5e5d792048e0b.png]: https://img-blog.csdnimg.cn/b413519f0e7c495290c5e5d792048e0b.png
[800abd9020114475a052e005ddbe1255.png]: https://img-blog.csdnimg.cn/800abd9020114475a052e005ddbe1255.png
[797eb3074b1b472c85a254740a7f3f54.png]: https://img-blog.csdnimg.cn/797eb3074b1b472c85a254740a7f3f54.png
[2226405eb517490bb658768624e6bfaa.png]: https://img-blog.csdnimg.cn/2226405eb517490bb658768624e6bfaa.png
[a112efee01d9441d9c435548ba92df15.png]: https://img-blog.csdnimg.cn/a112efee01d9441d9c435548ba92df15.png
[c151f19c38864819b68b3ccc9b1b7fde.png]: https://img-blog.csdnimg.cn/c151f19c38864819b68b3ccc9b1b7fde.png
[9849dc3f7bec4d189bfc81205767499b.png]: https://img-blog.csdnimg.cn/9849dc3f7bec4d189bfc81205767499b.png
[3e99f12cc3034e28bae0eb19037899d3.png]: https://img-blog.csdnimg.cn/3e99f12cc3034e28bae0eb19037899d3.png
[2575ef2c045640a383ea3ae182b7b706.png]: https://img-blog.csdnimg.cn/2575ef2c045640a383ea3ae182b7b706.png
[8feb7bd8bafa4c9fa4913534facf588e.png]: https://img-blog.csdnimg.cn/8feb7bd8bafa4c9fa4913534facf588e.png
[312872b095e9478892fbdf07f4336b69.png]: https://img-blog.csdnimg.cn/312872b095e9478892fbdf07f4336b69.png
[7bcd20f4716f4180ac081f40a6eab08d.png]: https://img-blog.csdnimg.cn/7bcd20f4716f4180ac081f40a6eab08d.png
[a16177a443f0452a8797b2c2715a5c9c.png]: https://img-blog.csdnimg.cn/a16177a443f0452a8797b2c2715a5c9c.png
[25fd536c3cc74e91a952043389e765a0.png]: https://img-blog.csdnimg.cn/25fd536c3cc74e91a952043389e765a0.png
[1b4db6a672ed4ce391cef85942e2dc9a.png]: https://img-blog.csdnimg.cn/1b4db6a672ed4ce391cef85942e2dc9a.png
[Link 1]: https://blog.csdn.net/GoodburghCottage/article/details/125929088
[Link 2]: https://blog.csdn.net/GoodburghCottage/article/details/125912135
[BF_--]: https://blog.csdn.net/GoodburghCottage/article/details/125907253
[Link 3]: https://blog.csdn.net/GoodburghCottage/article/details/125681654
[JAVA_]: https://blog.csdn.net/GoodburghCottage/article/details/125594490
[Linked _ - _ _]: https://blog.csdn.net/GoodburghCottage/article/details/125597183