前言
说起数组，大家肯定都是在熟悉不过了。我们在开发过程中，不管是使用的什么语言，肯定都使用过数组。平常我们都知道数组是一种数据类型，其实数组也是一种基本的数据结构。当数组作为数据结构来理解的时候，可能不太熟悉了。这里作为自己学习的笔记记录下数组这个数据结构的基本概念和应用。
什么是数组
数组可能我们都知道是什么，比如 js 中的[1,2,3]就是一个数组，但是这是一个数据类型，这里说下数组数据结构的定义：数组是一种线性表数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据。
什么是线性表
线性表就是数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。当然除了数组是线性表结构，与数组线性表相同结构的还有栈、队列、链表。除了有线性表结构，还有非线性表结构。比如：树、堆、图，之所以是非线性的，是因为数据不是前后线性连接的关系。
数组的特点
- 首先数组是一个连续的内存空间和相同类型的数据，因为有这两个特点，所以数组支持随机访问，效率非常高。但是因为有这两个特点，也就导致了数组数据结构数据的插入、删除变得非常的低效。因为有连续性的要求，有很多数据的移动操作影响性能。
- 数组是可以根据下标随机访问数据的，这个是什么原理呢？大概的原因就是：当定义一个数组时，计算机会在内存中分配一个空间用来存储数据。然后在这个分配的空间中进而切割更小的内存单元，用来存储数组中的每一个数据。每个存储单元对应一个内存地址，当需要随机访问某一个元素的时候，就通过这个地址来进行查询。
- 数组和链表的区别：
- 数组支持随机访问，并且根据下标访问的时间复杂度是$O(1)$，不适合插入和删除。
- 链表适合插入和删除，时间复杂度是$O(1)$，不适合查找。
为什么数组的插入和删除比较低效
前面我们提到，数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效。现在我们就来详细说一下，究竟为什么会导致低效？
插入
假设数组的长度为 n ，现在如果我们需要将一个数据插入到数组中的第 i 个位置。为了把第 i 个位置腾出来，给新来的数据，我们需要将第 i ～ n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢？如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 $O(1)$ 。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是$O(n)$。因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为 $(1+2+…n)/n=O(n)$ 。 如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 i 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第 i 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将 第 i 位的数据搬移到数组元素的最后，把新的元素直接放入第 i 个位置。利用这种处理技巧，在特定场景下，在第 i 个位置插入一个元素的时间复杂度就会降为$O(1)$。
删除
跟插入数据类似，如果我们要删除第 i 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 $O(1)$ ；如果删除开头的数据，则最坏情况时间复杂度为 $O(n)$ ；平均情况时间复杂度也为 $O(n)$ 实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率会提高很多
