数组

来自于:极客时间,数据结构与算法之美

定义

数组: 线性表数据结构。一组连续的内存空间,来存储一组具有相同类型的数据。

线性表

线性表上的数据最多只有前和后两个方向。链表 队列 栈 也是线性表结构

连续的内存空间 and 相同类型的数据

因为连续的内存空间 and 相同类型的数据,所以,数组可以随机访问。

数组支持随机访问的原因

插入

写一个数组插入的方法:

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
public class ArrayOperating {

public static void main(String[] args) {
ArrayOperating arrayOperating = new ArrayOperating();
int[] array = {1, 2, 4, 5, 5};
int[] newArray1 = arrayOperating.insertNewElement(array, 2, 999, Boolean.FALSE);
int[] newArray2 = arrayOperating.insertNewElement(array, 2, 999, Boolean.TRUE);
System.out.println(Arrays.toString(newArray1));
System.out.println(Arrays.toString(newArray2));
}

/**
* 数组指定位置插入元素
*
* @param index 位置
* @param value 值
* @param order 是否按照之前的顺序排列
*/
private int[] insertNewElement(int[] array, int index, int value, boolean order) {
int length = array.length;
if (index > length - 1) {
return array;
}
int[] newArray = Arrays.copyOf(array, length + 1);
if (order) {
for (int i = length; i > index; i--) {
newArray[i] = array[i - 1];
}
newArray[index] = value;
} else {
newArray[length] = newArray[index];
newArray[index] = value;
}
return newArray;
}
}

执行结果:

1
2
[1, 2, 999, 5, 5, 4]
[1, 2, 999, 4, 5, 5]

两种情况的处理:

  • 插入到指定位置,但是需要顺移
  • 只需要插入到指定位置

删除

如果将多次删除集中在一起执行,每次删除操作并不是真正的搬移数据,只是记录数据已经被删除,当数组没有更多的空间存储时,再触发一次性删除。减少了删除数据操作导致的数据搬移。

为什么数组下标从 0 开始

k 位置元素公式如下:

1
a[k]_address = base_address + k * type_size

type_size 为存储类型的大小,比如: int 为 4 。

如果是从 1 开始,则,计算公式为:

1
a[k]_address = base_address + (k-1) * type_size

每次多了一下减法运算。

Look at your mood.