数据结构之数组

基本概念

数组是一种数据结构,是有限个相同类型的变量所组成的有序集合,数组中的每一个变量被称为元素。

以整型数组为例,数组的存储形式如下图所示:

数据 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};
//打印数组中下标为4的元素
System.out.println(array[4]);

更新元素

更新元素也是非常简单的操作,直接利用下标就可以把新值赋给该元素。

简单的代码示例如下:

1
2
3
4
5
int[] array = new int[]{2,3,6,1,4,0,6,8,2};
//为数组下标为2的元素赋上新值
array[2] = 10;
//打印数组中下标为2的元素
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;

/**
* MyArray 构造方法
*
* @param capacity 初始容量
*/
public MyArray(int capacity) {
this.array = new int[capacity];
size = 0;
}

/**
* 插入元素
*
* @param index 下标
* @param element 元素
*/
public void insert(int index, int element) {
//判断下标是否超出范围
//此处判断的 index > size 并非数组越界,而是必须连续插入,例如实际有5个元素,插入下标为6的数据是不被允许的
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围!");
}
//从右向左循环,将元素逐个向右挪1位
//尾部插入时,该循环不会执行,因为尾部执行时 size - 1 >= index 永不成立
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;

/**
* MyArray 构造方法
*
* @param capacity 初始容量
*/
public MyArray(int capacity) {
this.array = new int[capacity];
size = 0;
}

/**
* 插入元素
*
* @param index 下标
* @param element 元素
*/
public void insert(int index, int element) {
//判断下标是否超出范围
//此处判断的 index > size 并非数组越界,而是必须连续插入,例如实际有5个元素,插入下标为6的数据是不被允许的
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围!");
}
//如果实际元素数量达到数组长度上限,则对数组进行扩容
if (size >= array.length) {
this.resize();
}

//从右向左循环,将元素逐个向右挪1位
//尾部插入时,该循环不会执行,因为尾部执行时 size - 1 >= index 永不成立
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所在的位置,然后再删除掉最后一个元素。

先替换再删除

这样一来,就无需进行大量的元素移动,复杂度有所降低。当然,这种方式并不是删除元素时主流的操作方式。

数组的优劣总结

数组拥有非常高效的随机访问能力,只要给出下标,就可以用常量时间找到对应元素。

至于数组的劣势,体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中,插入、删除元素都会导致大量元素被迫移动。影响效率。

总的来说,数组所适合的是读操作多、写操作少的场景。


参考文献:《小灰的算法之旅》—— 魏梦舒(@程序员小灰)