算法有多重要，看字节腾讯等公司面试多重视就行了

需要算法视频文档等，关注公众号：Java 架构师联盟，后台回复 Java 即可

1. 什么是数组？

数组是数据结构中最简单、最常用的数据结构，是一种线性表数据结构，在内存中是一块连续的存储空间，是有限个相同类型变量所组成的有序集合。数组中的每一个变量叫做元素。

线性表：线性表从字面意义上来理解是数据的排列像一条线的结构，只有前后两个方向。线性表中的元素都是一对一的关系，除了首尾元素外，其他元素都是首尾相连的。除了数组，链表、队列、栈也是线性表结构的。

以整型数组为例，我们 new 一个整型数组 int[] array = new int[]{1,2,3,4};，数组内的元素存储的元素是 1、2、3、4。那么数组的存储形势就如下图：

点击并拖拽以移动

​

在上图中粉色的格子代表已经被占用了的存储单元，绿色的格子代表数组的存储位置，白色的格子代表空闲的存储单元。数组的下标是从 0 开始的。所以元素和下标的对应关系是：

点击并拖拽以移动

​

2. 数组的优缺点

谈起数组的优点，我相信大部分的人都会说随机访问这个堪称杀手锏的特性，那么它为什么能够做到随机访问呢？

我认为主要有两点：

• 连续的存储空间

• 线性表结构

正因为它是在内存中是一块连续的存储空间，并且是线性表结构，前后元素都是一一对应的，所以才能够让他拥有随机访问的特性。在上一篇文章数据结构与算法-开篇当中我们介绍了时间复杂度和空间复杂度，这里就不对说了，比如我们要查找上边的数组中的第三个元素，那么打印出 array[2]就能够获取到第三个元素值，这里输出的是 3，因为数组支持随机访问，所以根据下标随机访问的时间复杂度为 O(1)，因为它的查找操作只执行了一次。

这样的结构使它的查询操作非常的方便，有利也有弊，它的插入、删除操作就会变得低效，因为要保证数据的连续性，所以执行插入、删除操作就需要做大量的数据搬移工作。如果这个时候一个数组的随机访问正好访问到没有值得下标上就会获取不到值。如果不搬移数据将中间的空洞补充上，那么内存就不连续了。我们在数组的操作中在详细介绍。

3. 数组的基本操作

3.1 添加元素

• 中间插入中间插入稍微复杂一些，每个元素都有自己的下标，如果一个元素想要插入到数组的中的除首尾的位置，那么插入的该位置上的元素都要向后移动，给新的位置腾出空间，保证连续性。

• 尾部插入尾部插入这种情况比较简单，直接把元素放到数组尾部的空闲位置即可，等同于更新元素的操作。

​

3.2 删除元素

删除操作和插入操作的过程正好相反，如果删除的元素在数组的中间，那么其后的元素都要向前移动。

点击并拖拽以移动

​

点击并拖拽以移动

​

3.3 更新元素

​

点击并拖拽以移动

​

这里更新元素的时间复杂度为 O(1)。

3.4 读取元素

点击并拖拽以移动

​

这里读元素的时间复杂度为 O(1)。

4. 容器能够代替数组吗？

针对数组类型，很多语言都提供了容器类，例如 Java 的 List，如果你是一个 Java 程序员，那么你应该清楚 ArrayList，对它应该非常的熟悉，和数组对比它有哪些优势呢？为什么开发的过程中经常使用它，最大的优势就是封装了对数组的操作，例如前面说的插入和删除，如果使用 ArrayList 还有一个优势是它支持动态扩容，当容器不够大的时候会自动扩容 1.5 倍，我们完全不需要关心底层的实现逻辑。那么什么时候使用数组更合适呢？有一下几点：

• ArrayList 无法存储基本数据类型，例如 int、long 需要封装为 Integer、Long。这里的装箱、拆箱操作有一定的性能损耗，如果特别关注性能，希望使用基本类型，那么就可以选择数组。

• 对数据只是简单的存储操作，那么选择数组效率更好些。

• 当做一些底层开发的时候数组可能用的比较多，比如一些框架。都是比较要求性能的。