1.什么是数组?
数组是有限个相同类型的变量所组成的有序集合,数组中的每一个变量被称为元素。数组是最为简单,最为常用的数据结构。
正如军队里的士兵存在编号一样,数组中的每一个元素也有着自己的下标,只不过这个下标是从0开始,一直到数组长度-1。
数组的另一个特点,是在内存中顺序存储,因此可以很好的实现逻辑上的顺序表。
2.数组在内存中的顺序存储,具体是什么样子呢?
内存是由一个个连续的内存单元组成的,每一个内存单元都有自己的地址。在这些内存单元中,有些被其他数据占用了,有些是空闲的。数组中的每一个元素,都存储在小小的内存单元中,且元素之间紧密排列,既不能打乱元素的存储顺序,也不能跳过某个存储单元进行存储。
3.数组的基本操作
数据结构的操作无非就是增,删,改,查4种情况,数组也是一样。
①.读取元素
对于数组来说,读取元素是最简单的操作。由于数组在内存中顺序存储,所以只要给出一个数组的下标,就可以读到对应的数组元素。
int[] array = new int[]{3,1,2,5,4,9,7,2}; //输出数组中下标为3的元素 System.out.println(array[3]);
②.更新元素
要把数组中的某一个元素的值替换为一个新值,也是非常简单的操作,直接利用数组下标就可以把新值赋给该元素。
int[] array = new int[]{3,1,2,5,4,9,7,2}; //给数组下标为5的元素赋值 array[5] = 10; //输出数组中下标为5的元素 System.out.println(array[5]);
③.插入元素
众所周知,数组的实际元素数量可能小于数组的长度;因此,插入数组元素的操作存在3种情况:
-
-
- 尾部插入
- 中间插入
- 超范围插入
-
a.尾部插入:是最简单的情况,直接把插入的元素放在数组尾部的空闲位置即可,等同于更新元素的操作。
b.中间插入:稍微复杂一些。由于数组的每一个元素都有其固定的下标,所以不得不首先把插入位置及后面的元素向后移动,腾出地方,再把要插入的元素放到对应的数组位置上。
/** * @Author Jack丶WeTa * @Date 2020/7/22 10:31 * @Description 数组插入元素-中间插入 */ public class MyArray { private int[] array; private int size; public MyArray(int capacity) { this.array = new int[capacity]; this.size = 0; } /** * 数组插入元素 */ public void insert(int index, int element) { //判断下表是否超出范围 if (index < 0 || index > size) {//由于数组中默认是顺序排列,并且默认值为0,因此此处就默认按照数组下标由低到高添加元素 throw new IndexOutOfBoundsException("超出数组实际元素范围!"); } //从右向左循环,将元素逐个向右挪一位 for (int i = size - 1; i >= index; i--) { array[i + 1] = array[i]; } //腾出的位置放置新元素 array[index] = element; size++; } /** * 输出数组 */ public void output(int arrayLength) { for (int i = 0; i < arrayLength; i++) { System.out.println(array[i]); } } public static void main(String[] args) { MyArray myArray = new MyArray(10); myArray.insert(0, 3); myArray.insert(1, 7); myArray.insert(2, 9); myArray.insert(3, 5); myArray.insert(1, 6); myArray.output(10); } }
代码中的成员变量size是数组实际元素的数量。如果插入元素在数组尾部,传入的下标参数index等于size;如果插入元素在数组中间后头部,则index小于size。如果传入的下标参数index大于size或者小于0,则认为非法输入,会直接抛出异常。
可是,如果数组不断插入新的元素,元素数量超过了数组的最大长度,数组岂不是要“撑爆”了,这时,就会有超范围插入的概念。
c.超范围插入:假如现在又一个长度为6的数组,已经装满了元素,这时还想插入一个新元素。这就涉及到数组的扩容了。但是数组在创建的时候已经确定了它的长度,这该如何做呢?此时,可以创建一个新的数组,长度是旧数组的2倍,再把旧数组中的元素统统复制过去,这样就实现了数组的扩容。相关代码实现:
/** * @Author Jack丶WeTa * @Date 2020/7/22 11:22 * @Description 代码中的成员变量size是数组实际元素的数量。 * 如果插入元素在数组尾部,传入的下标参数index等于size; * 如果插入元素在数组中间后头部,则index小于size。 * 如果传入的下标参数index大于size或者小于0,则认为非法输入,会直接抛出异常。 */ public class MyArrayDilatation { private int[] array; //数组实际元素数量 private int size; public MyArrayDilatation(int capacity) { this.array = new int[capacity]; this.size = 0; } /** * 数组插入元素 */ 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]; } //腾出的位置放置新元素 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(int arrayLength) { for (int i = 0; i < arrayLength; i++) { System.out.println(array[i]); } } /** * * @param index * @return deleteElement:被删除的元素 */ public int delete(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("超出数组实际元素范围!"); } int deleteElement = array[index]; //从左向右循环,将元素逐个向左挪1位 for (int i = index; i < size - 1; i++) { array[i] = array[i+1]; } size--; return deleteElement; } public static void main(String[] args) { MyArrayDilatation myArrayDilatation = new MyArrayDilatation(4); myArrayDilatation.insert(0, 3); myArrayDilatation.insert(1, 7); myArrayDilatation.insert(2, 9); myArrayDilatation.insert(3, 5); myArrayDilatation.insert(1, 6); myArrayDilatation.output(4 * 2); int deleteElement = myArrayDilatation.delete(2); System.out.println("==================被删掉的元素是:"+ deleteElement +"====================="); myArrayDilatation.output(4 * 2); } }
d.删除元素:数组的删除操作和插入操作的过程相反,如果删除的元素位于数组中间,其后的元素都需要向前挪动1位。
由于不涉及到扩容的问题,所以删除代码实现比插入操作要简单
/** * * @param index * @return deleteElement:被删除的元素 */ public int delete(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("超出数组实际元素范围!"); } int deleteElement = array[index]; //从左向右循环,将元素逐个向左挪1位 for (int i = index; i < size - 1; i++) { array[i] = array[i+1]; } size--; return deleteElement; }
4.时间复杂度分别为多少呢?
①.数组读取元素的时间复杂度为O(1);
②.数组更新元素的时间复杂度为O(1);
③.数组插入元素的操作包含两部分:数组扩容的时间复杂度O(n)和插入并移动元素的时间复杂度O(n),综合起来,插入元素的时间复杂度为O(n);
④.数组删除元素的操作只涉及到元素的移动,所以时间复杂度也为O(n)。
5.对于删除操作,其实还存在一种取巧的方式。我们都可以来思考一样,如果要求只是删除数组中的一个元素,那么就可以将要删除的元素复制到最后一个元素的位置,然后删掉最后一个元素。这样一来,无需进行大量的数据移动,时间复杂度降为O(1)。但是这种方式只做参考,并不是删除元素的主流的操作方式。
6.总结
数组这种数据结构有什么优势和劣势呢?
优势:数组拥有非常高效的随机访问能力,只要给出下标,就可以用常量时间找到对应元素。有一种高效查找元素的算法叫做二分查找,就是利用了数组的这个优势。
劣势:至于数组的劣势,体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中,插入和删除元素都会导致大量元素被迫移动,影响效率。
总的来说,数组所适合的是读操作多,写操作少的场景。