基本概念
数组是一种数据结构，是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。
以整型数组为例，数组的存储形式如下图所示：
| 数据 |
2 |
3 |
6 |
1 |
4 |
0 |
6 |
8 |
2 |
| 下标 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
如你所见，数组的每一个元素都存在一个相应的“编号”，就是下标。下标从0开始，一直到数组的长度-1。
数组在内存中是顺序存储的，而内存是由一个个连续的内存单元组成，每一个内存单元都有自己的地址。数组中的每一元素都存储在内存单元中，而且元素之间紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。
在上图中，巧克力黄色的格子代表空闲的存储单元，灰色的格子代表已占用的存储单元，而淡绿色的连续格子代表数组在内存中的位置。
读取元素
读取元素是数组最简单的操作，由于数组在内存中顺序存储，所以只要给出一个数组下标，就可以读取到对应的数组元素。
假设有一个名为array的数组，想要读取数组下标为4的元素，就写作array[4]。
值得注意的是，输入的下标必须在数组的长度范围之内，否则会出现数组越界！如果数组的长度为x，输入的下标为y，那么结合下标从0开始的特点，就可以得出ymax=x-1。
简单的代码示例如下：
1
2
3
| int[] array = new int[]{2,3,6,1,4,0,6,8,2};
System.out.println(array[4]);
|
更新元素
更新元素也是非常简单的操作，直接利用下标就可以把新值赋给该元素。
简单的代码示例如下：
1
2
3
4
5
| int[] array = new int[]{2,3,6,1,4,0,6,8,2};
array[2] = 10;
System.out.println(array[2]);
|
插入元素
尾部插入
尾部插入是最简单的情况，直接把要插入的元素放在数组尾部的空闲位置即可，等同于更新元素的操作。
中间插入
中间插入稍微复杂一些，那是因为数组的每一个元素都有其固定的下标，所以不得不首先把插入位置以及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。
示例代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| public class MyArray {
private int[] array;
private int size;
public MyArray(int capacity) {
this.array = new int[capacity];
size = 0;
}
public void insert(int index, int element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = element;
size++;
}
public void output() {
for (int i = 0; i < size; i++) {
System.out.println(array[i]);
}
}
public static void main(String[] args) {
MyArray myArray = new MyArray(10);
myArray.insert(0, 3);
myArray.insert(1, 6);
myArray.insert(2, 9);
myArray.insert(3, 4);
myArray.insert(1, 1);
myArray.output();
}
}
|
超范围插入
如果数组不断插入新的元素，元素数量超过了数组的最大长度，数组就会被“撑爆”，这个就是接下来要研究的情况 —— 超范围插入。
假如现在有一个长度为10的数组，已经装满了元素，这时还想插入一个新元素，就必须对数组进行扩容操作。关键在于数组的长度在创建时就已确定，而且不能随意的变长或者变短，这该如何是好？
此时可以创建一个新的数组，长度是旧数组的2倍（此处的2倍并不代表Java的扩容机制为2倍，仅为举例说明！），再把旧数组的所有元素全部复制到新数组，这样就实现了数组的扩容。
示例代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| public class MyArray {
private int[] array;
private int size;
public MyArray(int capacity) {
this.array = new int[capacity];
size = 0;
}
public void insert(int index, int element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
if (size >= array.length) {
this.resize();
}
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
array[index] = element;
size++;
}
public void resize() {
int[] newArray = new int[array.length * 2];
System.arraycopy(array, 0, newArray, 0, array.length);
array = newArray;
}
public void output() {
for (int i = 0; i < size; i++) {
System.out.println(array[i]);
}
}
public static void main(String[] args) {
MyArray myArray = new MyArray(4);
myArray.insert(0, 3);
myArray.insert(1, 6);
myArray.insert(2, 9);
myArray.insert(3, 4);
myArray.insert(4, 1);
myArray.output();
}
}
|
删除元素
数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后的元素都需要向前挪动1位。与插入元素相比更简单的是，删除元素不涉及扩容问题。
示例代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
int deletedElement = array[index];
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
size--;
return deletedElement;
}
|
对于删除操作，还存在一种取巧的方式，前提是数组元素没有顺序要求。例如下图所示，需要删除的是数组中的元素8，可以把最后一个元素4复制替换到到元素8所在的位置，然后再删除掉最后一个元素。
这样一来，就无需进行大量的元素移动，复杂度有所降低。当然，这种方式并不是删除元素时主流的操作方式。
数组的优劣总结
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。
至于数组的劣势，体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动。影响效率。
总的来说，数组所适合的是读操作多、写操作少的场景。
参考文献：《小灰的算法之旅》—— 魏梦舒（@程序员小灰）
