class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">

JDK提供的顺序表有：java.util.ArrayList 其底层实现就是数组

数组（顺序表）时间复杂度分析：

1. 查询get(i) ，不难看出不论数据元素量N有多大，只需要一次eles[i] 就可以获取到对应的元素，所以时间复杂度为O(1)
2. 插入insert(int i, T t)，每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂度为O(n)
3. 删除元素remove(int i)，每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大，移动的元素也越多，时间复杂度为O(n)
4. 数组长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显

优点： 

1. 按照索引查询元素速度快 
2. 按照索引遍历数组方便

缺点：  

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

适用场景： 

• 频繁查询，对存储空间要求不大，很少增加和删除的情况

2、栈

栈是一种基于先进后出（FILO）的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

JDK提供的栈有：java.util.Stack 

应用场景：

括号匹配问题；逆波兰表达式求值问题；实现递归功能方面的场景，例如斐波那契数列。

3、队列

队列是一种基于先进先出（FIFO）的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先被读取出来。

JDK提供的队列接口有：java.util.Queue

使用场景：

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

4、链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结节（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 

链表时间复杂度分析：

• get(int i)：每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)
• insert(int i, T t)：每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)
• remove(int i)：每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)

链表 VS 数组（顺序表比较）

相比较数组（顺序表），链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作，同时它并没有涉及的元素的交换。

相比较数组（顺序表），链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用数组（顺序表），增删操作比较多，建议使用链表。

链表的优点： 

链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素； 

添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点： 

因为含有大量的指针域，占用空间较大； 

查找元素需要遍历链表来查找，非常耗时。

JDK提供的链表有：java.util.LinkedList

适用场景： 

数据量较小，需要频繁增加，删除操作的场景；

快慢指针：求中间值问题、单向链表是否有环问题、有环链表入口问题；

循环链表：约瑟夫问题

5、树

树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构等等。

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

树具有以下特点：

1. 每个结点有零个或多个子结点；
2. 没有父结点的结点为根结点；
3. 每一个非根结点只有一个父结点；
4. 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树； 

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树、平衡树、红黑树、B树、B+树

应用场景：

1. JDK1.8中 HashMap的底层源码中用到了数组+链表+红黑树；
2. 磁盘文件中使用B树做为数据组织，B树大大提高了IO的操作效率；
3. mysql数据库索引结构采用B+树；

6、散列表

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

记录的存储位置=f(key)

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

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

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

JDK提供的哈希表有：java.util.HashMap

散列表应用场景：

1. 哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
2. 解决哈希冲突问题：1 可以对数组扩容； 2 优化hash计算方式；

7、堆

堆是计算机学科中一类特殊的数据结构的统称，堆通常可以被看作是一棵完全二叉树的数组对象。

堆的特性：

1. 它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满；
2. 它通常用数组来实现；

堆应用场景：

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

8、图

图的定义：图是由一组顶点和一组能够将两个顶点相连的边组成的

图的搜索：

1. 深度优先搜索：指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。
2. 广度优先搜索：指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。

图的应用场景：

1. 道路畅通工程
2. 最短路径

文章最后，给大家推荐一些受欢迎的技术博客链接：

1. JAVA相关的深度技术博客链接
2. Flinak 相关技术博客链接
3. Spark 核心技术链接
4. 设计模式 —— 深度技术博客链接
5. 机器学习 —— 深度技术博客链接
6. Hadoop相关技术博客链接
7. 超全干货--Flink思维导图，花了3周左右编写、校对
8. 深入JAVA 的JVM核心原理解决线上各种故障【附案例】
9. 请谈谈你对volatile的理解？--最近小李子与面试官的一场“硬核较量”
10. 聊聊RPC通信，经常被问到的一道面试题。源码+笔记，包懂
11. 深入聊聊Java 垃圾回收机制【附原理图及调优方法】

欢迎扫描下方的二维码或 搜索 公众号“大数据高级架构师”，我们会有更多、且及时的资料推送给您，欢迎多多交流！

发表评论

登录后才能发表评论和回复 注册

/ 登录

提交评论

评论记录：

未查询到任何数据！

回复评论：

×

关闭 提交评论