鸡汤
人生没有连续的一帆风顺，总是要靠自己的坚持来维护这一份延续
一段连续的快乐总是那么不容易被插入或打断
1、前言
在复习数据之前，我们先回忆一个概念，什么是线性表，线性表和数组的关系是什么？接下来让我们一起来回顾一下
2、线性表
定义：零个或多个数据元素组成的有限序列。
解释：我们注意定义中有两个点，一个是数据元素，一个是有限序列。首先线性表是一个序列，强调这个序列是有限长度n，其中n≥0, n=0的序列我们成为空表；数据元素则是一个抽象的概念，数据元素可能是数字1、2、3，可能是猴、狗等动物，也可能是本子、笔等文具。
3、数组与线性表的关系
数据是线性表的顺序存储结构，即用一段连续的存储单元一次存储线性表的数据元素。有两个概念我们要区分一下，“数组的长度”和“线性表的长度”是有区别的，一般来说，数组的长度要大于等于线性表的长度，简单可以理解为我们在一些高级语言中看到的长度（len）和容量（cap），数组是存储线性表的存储空间，已经分配的存储空间一般是不会变的。当然一些高级语言中会通过某些编程的手段使数组实现动态分配，但这是很消耗的，所以在我们日常的开发中，都会尽量避免数组的重新分配。
1 | // 假如已知arr1数组长度，需要申请一个和arr1相同长度的数据 |
4、数组的地址计算
由于数组是顺序存储的，所以数组的地址也就是连续的一段空间，我们在编程语言中的往往定义起始地址是0，这有悖于我们从小接受的从1开始数数的教育。于是线性表的第i个元素在顺序存储结构中的位置应该是i - 1，即数据元素的序列号与存储的位置如下图
5、数组的插入与删除
5.1 数据元素检索
对于顺序存储结构来说，获取某一个位置的元素是很容易的，譬如，我们要获取第i个元素，我们只需要将第i-1位置的元素去除即可，这里的时间复杂度为O(1)。
5.2 数据元素插入
上面我们说到了，从数组中取一个位置的数据是很容易的，那么插入呢？我们可以想象一下，在课堂的一排座位是一个数组，那么现在新来一位同学，他要选择这一排的某个位置上，我们都要怎么做呢，首先这位新同学要选的位置是符合老师的期望的，然后要看这一排的座位是否足够容纳这位新同学，如果不够，我们就要搬来一个座位来满足需求，假如新同学选的是第i个位置，那么为了保持这一排的其他同学顺序不变，只能从最后一位同学开始到第i个同学，依次向后移动一个位置，空出来的新第i位置留给新同学。由此我们知道，将一个数据元素插入数组，我们需要做这些事：
- 判断要插入的位置是否合理，不合理抛出异常
- 如果插入后的数据元素个数大于数组长度，那么就需要返回异常或者动态申请新的存储空间
- 从最后一个数据元素开始，到第i位置的元素，依次向后移动一个存储单元
- 第i位置赋值为要插入的元素
// 代码过于简单，忽略
5.3 数据元素删除
同插入的场景中提到的，那么删除的过程自然就是插入的逆序，还用刚才的例子，假如这个新来的同学在第i位置坐的很不爽，前后的同学总是合谋欺负他，那么他要离开这个位置换到其他排，那么从第i+1位置开始，都需要依次向前移动一个位置，并将最后一个位置元素清除（线性表长度减1）
- 判断要删除的位置是否合理，不合理抛出异常
- 从第i+1个数据元素到最后一个数据元素，依次向前移动一个存储单元
- 线性表长度减1
6、数组的优劣势
优势：
- 快速获取线性表中的任意位置数据元素
- 数据元素顺序存储，不需要维护数据元素之间的关联关系（利用物理内存位置维护，地址依次递增）
劣势：
- 插入和删除操作需要移动线性表中的大多数数据元素
- 线性表长度大于分配的存储空间时，需要重新申请存储空间，性能有比较大的消耗
- 存储空间连续，当线性表的长度很大是，内存分配是个问题
