2.1 什么是数组
2.1.1 初识数组
这些特点是如何体现的呢？
参加过军训的读者，一定都记得这样的场景。
在军队里，每一个士兵都有自己固定的位置、固定的编号。众多士兵紧密团结在一起，高效地执行着一个个命令。
大黄，咱们为什么要说这么多关于军队的事情呢？
因为有一个数据结构就像军队一样整齐、有序，这个数据结构叫作数组 。
什么是数组？
数组对应的英文是array，是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。
以整型数组为例，数组的存储形式如下图所示。
正如军队里的士兵存在编号一样，数组中的每一个元素也有着自己的下标，只不过这个下标从0开始，一直到数组长度-1。
数组的另一个特点，是在内存中顺序存储 ，因此可以很好地实现逻辑上的顺序表 。
数组在内存中的顺序存储，具体是什么样子呢？
内存是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址。在这些内存单元中，有些被其他数据占用了，有些是空闲的。
数组中的每一个元素，都存储在小小的内存单元中，并且元素之间紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。
在上图中，橙色的格子代表空闲的存储单元，灰色的格子代表已占用的存储单元，而红色的连续格子代表数组在内存中的位置。
不同类型的数组，每个元素所占的字节个数也不同，本图只是一个简单的示意图。
那么，我们怎样来使用一个数组呢？
数据结构的操作无非是增、删、改、查4种情况，下面让我们来看一看数组的基本操作。
2.1.2 数组的基本操作
1. 读取元素
对于数组来说，读取元素是最简单的操作。由于数组在内存中顺序存储，所以只要给出一个数组下标，就可以读取到对应的数组元素。
假设有一个名称为array的数组，我们要读取数组下标为3的元素，就写作array[3]；读取数组下标为5的元素，就写作array[5]。需要注意的是，输入的下标必须在数组的长度范围之内，否则会出现数组越界。
像这种根据下标读取元素的方式叫作随机读取 。
简单的代码示例如下：
1. int[] array = new int[]{3,1,2,5,4,9,7,2};
2. // 输出数组中下标为3的元素
3. System.out.println(array[3]);
2. 更新元素
要把数组中某一个元素的值替换为一个新值，也是非常简单的操作。直接利用数组下标，就可以把新值赋给该元素。
简单的代码示例如下：
1. int[] array = new int[]{3,1,2,5,4,9,7,2};
2. // 给数组下标为5的元素赋值
3. array[5] = 10;
4. // 输出数组中下标为5的元素
5. System.out.println(array[5]);
小灰，咱们刚刚讲过时间复杂度的概念，你说说数组读取元素和更新元素的时间复杂度分别是多少？
嘿嘿，这难不倒我。数组读取元素和更新元素的时间复杂度都是O(1) 。
3. 插入元素
在介绍插入数组元素的操作之前，我们需要补充一个概念，那就是数组的实际元素数量有可能小于数组的长度，例如下面的情形。
因此，插入数组元素的操作存在3种情况。
尾部插入
中间插入
超范围插入
尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作。
中间插入，稍微复杂一些。由于数组的每一个元素都有其固定下标，所以不得不首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。
中间插入操作的完整实现代码如下：
1. private int[] array;
2. private int size;
3.
4. public MyArray(int capacity){
5. this.array = new int[capacity];
6. size = 0;
7. }
8.
9. /**
10. * 数组插入元素
11. * @param element 插入的元素
12. * @param index 插入的位置
13. */
14. public void insert(int element, int index) throws Exception {
15. //判断访问下标是否超出范围
16. if(index<0 || index>size){
17. throw new IndexOutOfBoundsException("超出数组实际元素范围！");
18. }
19. //从右向左循环，将元素逐个向右挪1位
20. for(int i=size-1; i>=index; i--){
21. array[i+1] = array[i];
22. }
23. //腾出的位置放入新元素
24. array[index] = element;
25. size++;
26. }
27.
28. /**
29. * 输出数组
30. */
31. public void output(){
32. for(int i=0; i
33. System.out.println(array[i]);
34. }
35. }
36.
37. public static void main(String[] args) throws Exception {
38. MyArray myArray = new MyArray(10);
39. myArray.insert(3,0);
40. myArray.insert(7,1);
41. myArray.insert(9,2);
42. myArray.insert(5,3);
43. myArray.insert(6,1);
44. myArray.output();
45. }
代码中的成员变量size是数组实际元素的数量。如果插入元素在数组尾部，传入的下标参数index等于size；如果插入元素在数组中间或头部，则index小于size。
如果传入的下标参数index大于size或小于0，则认为是非法输入，会直接抛出异常。
可是，如果数组不断插入新的元素，元素数量超过了数组的最大长度，数组岂不是要“撑爆”了？
问得很好，这就是接下来要讲的情况——超范围插入。
超范围插入，又是什么意思呢？
假如现在有一个长度为6的数组，已经装满了元素，这时还想插入一个新元素。
这就涉及数组的扩容 了。可是数组的长度在创建时就已经确定了，无法像孙悟空的金箍棒那样随意变长或变短。这该如何是好呢？
此时可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素统统复制过去，这样就实现了数组的扩容。
如此一来，我们的插入元素方法也需要改写了，改写后的代码如下：
1. private int[] array;
2. private int size;
3.
4. public MyArray(int capacity){
5. this.array = new int[capacity];
6. size = 0;
7. }
8.
9. /**
10. * 数组插入元素
11. * @param element 插入的元素
12. * @param index 插入的位置
13. */
14. public void insert(int element, int index) throws Exception {
15. //判断访问下标是否超出范围
16. if(index<0 || index>size){
17. throw new IndexOutOfBoundsException("超出数组实际元素范围！");
18. }
19. //如果实际元素达到数组容量上限，则对数组进行扩容
20. if(size >= array.length){
21. resize();
22. }
23. //从右向左循环，将元素逐个向右挪1位
24. for(int i=size-1; i>=index; i--){
25. array[i+1] = array[i];
26. }
27. //腾出的位置放入新元素
28. array[index] = element;
29. size++;
30. }
31.
32. /**
33. * 数组扩容
34. */
35. public void resize(){
36. int[] arrayNew = new int[array.length*2];
37. //从旧数组复制到新数组
38. System.arraycopy(array, 0, arrayNew, 0, array.length);
39. array = arrayNew;
40. }
41.
42. /**
43. * 输出数组
44. */
45. public void output(){
46. for(int i=0; i
47. System.out.println(array[i]);
48. }
49. }
50.
51. public static void main(String[] args) throws Exception {
52. MyArray myArray = new MyArray(4);
53. myArray.insert(3,0);
54. myArray.insert(7,1);
55. myArray.insert(9,2);
56. myArray.insert(5,3);
57. myArray.insert(6,1);
58. myArray.output();
59. }
4. 删除元素
数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。
由于不涉及扩容问题，所以删除操作的代码实现比插入操作要简单：
1. /**
2. * 数组删除元素
3. * @param index 删除的位置
4. */
5. public int delete(int index) throws Exception {
6. //判断访问下标是否超出范围
7. if(index<0 || index>=size){
8. throw new IndexOutOfBoundsException("超出数组实际元素范围！");
9. }
10. int deletedElement = array[index];
11. //从左向右循环，将元素逐个向左挪1位
12. for(int i=index; i
13. array[i] = array[i+1];
14. }
15. size--;
16. return deletedElement;
17. }
小灰，我再考考你，数组的插入和删除操作，时间复杂度分别是多少？
先说说插入操作，数组扩容的时间复杂度是O(n)，插入并移动元素的时间复杂度也是O(n)，综合起来插入操作的时间复杂度是O(n) 。至于删除操作，只涉及元素的移动，时间复杂度也是O(n) 。
说得没错。对于删除操作，其实还存在一种取巧的方式，前提是数组元素没有顺序要求。
例如下图所示，需要删除的是数组中的元素2，可以把最后一个元素复制到元素2所在的位置，然后再删除掉最后一个元素。
这样一来，无须进行大量的元素移动，时间复杂度降低为O(1)。当然，这种方式只作参考，并不是删除元素时主流的操作方式。
2.1.3 数组的优势和劣势
数组的基本知识我懂了，那么，使用数组这种数据结构有什么优势和劣势呢？
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找，就是利用了数组的这个优势。
至于数组的劣势，体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。
总的来说，数组所适合的是读操作多、写操作少 的场景，下一节我们要讲解的链表则恰恰相反。好了，让我们下一节再会！