手撕数据结构与算法-数组

前言

开篇一张图，知识全靠吹！

本系列文章已收录到github：

1. 什么是数组？

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

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

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

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

2. 数组的优缺点

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

我认为主要有两点：

连续的存储空间 线性表结构

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

3. 数组的基本操作

3.1 添加元素

中间插入 中间插入稍微复杂一些，每个元素都有自己的下标，如果一个元素想要插入到数组的中的除首尾的位置，那么插入的该位置上的元素都要向后移动，给新的位置腾出空间，保证连续性。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YlR0tL5l-1575253810973)(https://s2.ax1x.com/2019/11/30/QZtetx.png)] 尾部插入 尾部插入这种情况比较简单，直接把元素放到数组尾部的空闲位置即可，等同于更新元素的操作。

3.2 删除元素

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

3.3 更新元素

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

3.4 读取元素

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

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

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

5. 参考

《漫画算法》

《数据结构与算法之美》

注意、注意 前方高能======>

来了 来了 他来了 他带着二维码来了！！！