说到数组这种数据结构，我相信绝大多数的开发工程师都在实际工作中用到过或看到过。甚至大部分工程师都觉得这个玩意儿有什么好说的，太基础、太简单了。我想说的是，尽管数组的确是非常的基础，但是他并不简单。
1.到底才什么是数组？
到底什么才是数组，我相信很多人心目中都有不同的认识。但是我还是想引用一段专业的解释来说明一下什么才是数组：
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
1.1数组的特性
在刚才看到的解释中，我们看到了数组的几个特性：
- 线性表数据结构
- 使用连续的内存空间
- 存储相同类型的数据
1.1.1线性表数据结构
所谓的线性表数据结构就是数据只有前后两个方向，说几种比较常见的线性表数据结构吧。
| 数组 | 队列 | 队列 | 链表 |
|---|---|---|---|
通过观察这几种数据我们可以得知，这些数据结构他们每个元素和其他元素之间只有唯一的前后对应的关系。如果你看到这里对这个概念还有点模糊的话。那我再给你对应的说一下非线性表数据结构你肯定就明白了。
非线性表数据结构比较特点的几个数据类型包括：
- 二叉树
- 堆
- 图
我们比较发现，这些非线性表数据结构的数据类型，每个节点都可能后面跟着多个节点，换句话说他不仅仅有前后两个方向。比如说二叉树，他的后面的节点包括左节点和右节点。这就不符合线性表数据结构的只有前后两个方向的定义了。
1.1.2连续内存空间
数组在内存中创建的时候要求使用连续的内存空间。这个很好理解，举一个极端的例子：
我们内存中有1.2GB的空闲空间，但是这些空闲空间是非连续的，可用的空闲空间的连续大小分别为0.7GB和0.5GB，这个时候如果我们想船舰一个1GB大小的数组是无法创建的。虽然空闲空间的总大小高达1.2GB，但是由于其连续的内存空间不足1GB，所以数组无法创建。
1.1.3存储相同的数据类型
数组在创建的时候已经规定好了存储的数据类型，所以他只能存储相同的数据类型。说到这里是不是感觉这个数组怎么“毛病”这么多，真难伺候。但是正是因为他的这些特性，数组拥有一个堪称“杀手锏”的特性随机访问。
2.细说数组的优缺点
其实很多朋友在面试的时候都会被问到这么一个问题：
兄弟，你能说一说ArrayList和LinkedList的区别吗？他们分别适用于哪种场景啊？
其实这个问题本质上就是问的链表和数组的区别已经他们的应用场景。我见过很多人很肯定的告诉我：
LinkedList是链表结构，适合插入和删除多、查询少的场景，ArrayList的底层是数组，适合查询多，插入和删除少的场景。甚至还会告诉我查询数组的时间复杂度是O(1) 。其实这种说法不严谨。因为数组的随机访问的特性，我们可以说数据在使用下标访问的时候，其时间复杂度是O(1)，但是如果我们是按照值的方式去查询数组，那么就算是通过二分查找去查找一个有序数组，时间复杂度也是O(logn)。
说到这里我们就得好好来谈谈数组的这个杀手锏级别的特性随机访问了。
2.1 快速的“随机访问”
随机访问的时间复杂度为什么是O(1)呢？这还是因为数组的特性导致的，因为前面我们说过数组的特性之二连续的内存空间、存储相同的数据类型。
举个例子：
我们创建一个数组大小为10的int类型的数组
int[] items = new int[10];
for(int i = 0 ; i < 10 ; ++i){
items[i] = i;
}
假设内存中的起始位置是100，那么items所占用内存是100~139。为什么是这一块内存呢？因为int的大小为4，10个就是40，从起点为100开始，那么结束的位置就是139。是不是感觉有点绕，我们来画个图来表示吧。
从这个图中我们看出什么规律，每个下标所在的开始内存位置都是上一个元素的结束位置+1，而且大小都是一致的。那我们假设数组的位置是x，下标为i，数组中存储的元素大小为n，那么我们根据随机访问的内存地址就是：
x + i * n
结合我们这个例子开看的话，如果我们想要获取item[2]的元素，那么他的内存位置就是100 + 2 * 4 = 108。我们直接访问这个地址的数据就可以拿到元素了，这就是为什么说随机访问的时间复杂度是O(1)。
说完了数组的随机访问，那我们再来看看为啥常说数组不适合大量的插入和删除操作
2.2 令人蛋疼的“插入和删除”
其实说数组不适合大量的删除和插入操作的原因还是因为数组要求连续的内存空间，正是成也萧何败也萧何。还是刚才这个例子：原始数组items中的元素的按照下标顺序分别是 0 1 2 3 4 5 6 7 8 9，好了，现在我们希望将5删除掉，使其变成0 1 2 3 4 6 7 8 9 9,那我们需要怎么做呢？根据其要求连续的内存空间的特性上。代码上我们需要这么做
public void remove(int[] items, int index) {
if (items.length - 1 < index) {
return;
}
int i = index;
for (; i < items.length - 1; i++) {
items[i] = items[i + 1];
}
}
通过代码我们可以看到，我只是删除了一个元素，但是却触发了大量的迁移操作。插入也是这样的道理。举个例子：
public static void insert(int[] items, int index, int val) {
for (int i = items.length - 1; i > index; i--) {
int temp = items[i];
items[i] = items[i - 1];
items[i - 1] = temp;
}
items[index] = val;
}
public static void main(String[] args) {
int[] items = new int[]{0,1,2,3,4,6,7,8,9,0};
// 我希望在下标为5的地方插入元素为5，使数组中的元素变为 0 1 2 3 4 5 6 7 8 9
ArrayDemo.insert(items,5,5);
System.out.println(Arrays.toString(items));
}
// sout [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2.3 删除和插入的小技巧
难道说每次删除和插入都必须得做数据的搬移吗？就没有其他的办法吗？其实在特定情况下是有的。
2.3.1 插入的小技巧
如果对插入的数据没有排序要求的话，我们可以这么做：假设我们原始的数组为结构为0 1 2 3 4 5 6 0 0 0，我们希望在4之前插入一个元素7，但是对插入之后的排序没有要求，我们可以这样做，将原始下标为4的元素取出来放到7的位置，然后将7插入4的位置。是不是感觉有点乱。我们来看代码：
/**
* 在数组下标为index的位置插入元素val
* @param items 数组
* @param size 数组中元素的个数
* @param index 希望插入的位置
* @param val 希望插入的值
*/
public static void insert(int[] items, int size, int index,int val) {
if (size + 1 == items.length) {
return;
}
int temp = items[index];
items[index] = val;
items[size + 1] = temp;
}
public static void main(String[] args) {
int[] items = new int[10];
for (int i = 0; i < 6; i++) {
items[i] = i;
}
ArrayDemo.insert(items,5,4,7);
System.out.println(Arrays.toString(items));
}
// sout [0, 1, 2, 3, 7, 5, 4, 0, 0, 0]
我们这里只搬移了一次数据就完成了插入。
2.3.2 删除的小技巧
刚才我们说了插入的小技巧，那么删除有小技巧吗？其实也是有的。
数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。为了避免触犯三次数据的搬移操作，我们可以先暂时将abc三个元素记录下来，并不是真正的删除，当数组没有空间存储数据的时候，我们才真正的触发删除操作。
3. 为什么数组的下标要从0开始？
这个问题我看网上有很多结论，大致分为两种：
- 因为随机下标的计算公式，如果是从1开始的话，那么计算公式每次计算的时候得额外执行一次i-1的操作，而且这个下标记录的是offset，是偏移量，从0开始没有问题啊
- 历史原因，因为C中的数组是从0开始的，后面的编程语言也跟着大佬混。也是0开始
你更支持哪一种说法呢？