目录
- 数组：随机读取，顺序存储
- 1. 读取数据
- 2. 更新元素
- 3. 插入元素
- 3.1. 尾部插入
- 3.2. 中间插入
- 3.1. 超范围输入
- 4. 删除元素
内容大部分摘自下《漫画算法 小灰的算法之旅》，加了自己的一部分想法
java的数组复制方法System.arraycopy()的使用说明
数组：随机读取，顺序存储
1. 读取数据
int array = {1,2,3,4,5}
array[index]
2. 更新元素
int array = {1,2,3,4,5}
array[index]=newValue
数组读取元素和更新元素的时间复杂度都是O(1) 。
3. 插入元素
==在介绍插入数组元素的操作之前，我们需要补充一个概念，那就是数组
的实际元素数量有可能小于数组的长度，这里很重要。==例如下面的情形。
因此，插入数组元素的操作存在3种情况。
- 尾部插入
- 中间插入
- 超范围插入
3.1. 尾部插入
尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位
置即可，等同于更新元素的操作。
3.2. 中间插入
中间插入，稍微复杂一些。由于数组的每一个元素都有其固定下标，所
以不得不首先把插入位置及后面的元素向后移动，腾出地方，再把要插
入的元素放到对应的数组位置上。
public class MyArray3 {
private static int aa;
private int[] array;
private int size;
public MyArray3(int capacity) {
this.array = new int[capacity];
size = 0;
}
public static void main(String[] args) throws Exception {
MyArray3 myArray3 = new MyArray3(10);
// myArray2.insert(-1, 8); //超出数组实际元素范围！
// myArray2.insert(3, 8); //超出数组实际元素范围！
myArray3.insert(0, 3);
myArray3.insert(1, 7);
myArray3.insert(2, 9);
myArray3.insert(3, 5);
myArray3.insert(1, 6);
myArray3.output();
}
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];
}
// System.arraycopy(array, index, array, index + 1, size - index);
//腾出的位置放入新元素
array[index] = element;
size++;
}
public void output() {
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
}
}
代码中的成员变量size是数组实际元素的数量。如果插入元素在数组尾
部，传入的下标参数index等于size；如果插入元素在数组中间或头部，
则index小于size。
如果传入的下标参数index大于size或小于0，则认为是非法输入，会直
接抛出异常。
3.1. 超范围输入
假如现在有一个长度为6的数组，已经装满了元素，这时还想插入一个
新元素。
这就涉及数组的扩容了。可是数组的长度在创建时就已经确定了，无
法像孙悟空的金箍棒那样随意变长或变短。这该如何是好呢？
此时可以创建一个新数组，长度是旧数组的2倍，再把旧数组中的元素
统统复制过去，这样就实现了数组的扩容。
public class MyArray4 {
private int[] array;
private int size;
public MyArray4(int capacity) {
this.array = new int[capacity];
size = 0;
}
public static void main(String[] args) throws Exception {
MyArray4 myArray4 = new MyArray4(4);
//myArray4.insert(-1, 8); //超出数组实际元素范围！
//myArray4.insert(3, 8); //超出数组实际元素范围！
myArray4.insert(0, 3);
myArray4.insert(1, 7);
myArray4.insert(2, 9);
myArray4.insert(3, 5);
myArray4.insert(1, 6);
myArray4.insert(5, 8); //超出数组长度4
myArray4.output();
}
public void insert(int index, int element) {
//判断访问下标是否超出范围
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
//如果实际元素达到数组容量上线，数组扩容
if (size >= array.length) {
resize();
}
//从右向左循环，逐个元素向右挪一位。
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
// System.arraycopy(array, index, array, index + 1, size - index);
//腾出的位置放入新元素
array[index] = element;
size++;
}
public void resize() {
int[] arrayNew = new int[array.length * 2];
//从旧数组拷贝到新数组
for (int i = 0; i < size; i++) {
arrayNew[i] = array[i];
}
// System.arraycopy(array, 0, arrayNew, 0, array.length);
array = arrayNew;
}
public void output() {
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
}
}
4. 删除元素
数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中
间，其后的元素都需要向前挪动1位。
public int delete(int index) throws Exception {
//判断访问下标是否超出范围
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];
}
// System.arraycopy(array, index + 1, array, index, size - 1 - index);
size--;
return deletedElement;
}
