基本概念
数组是一种数据结构,是有限个相同类型的变量所组成的有序集合,数组中的每一个变量被称为元素。
以整型数组为例,数组的存储形式如下图所示:
数据 |
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所在的位置,然后再删除掉最后一个元素。

这样一来,就无需进行大量的元素移动,复杂度有所降低。当然,这种方式并不是删除元素时主流的操作方式。
数组的优劣总结
数组拥有非常高效的随机访问能力,只要给出下标,就可以用常量时间找到对应元素。
至于数组的劣势,体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中,插入、删除元素都会导致大量元素被迫移动。影响效率。
总的来说,数组所适合的是读操作多、写操作少的场景。
参考文献:《小灰的算法之旅》—— 魏梦舒(@程序员小灰)