学习笔记——数据结构:数组
来简单总结一下这几天学的数组,数组虽然从一接触java开始就在用,但是没有学习过数组本身。
目录
1. 什么是数组?
数组是编程语言最常见的一种线性表的数据结构。
他用一种连续的内存空间,来存储相同的数据类型。
关键点:
线性表:数据排成像线一样得结构。数据间有前后关系。
连续的内存空间和相同的数据类型:随机访问。这也是数组查询效率高的原因。
2. 数组怎么用?
使用数组前要初始化数组。
两种初始化方式:
例:静态初始化:int[ ] arr = new int[ ]{1, 2, 3, 4}; 直接给定元素
例:动态初始化:int[ ] arr = new int[ 4]; 给定数组容量为四个
【从可读性角度来说,不推荐 int arr[ ] 这种格式】
数组的使用:
数组通过下标(从0开始)随机访问:
int[ ] arr = new int[ ]{1, 2, 3, 4};
System.out.println(int[1]); //输出:2
通过下标赋值:
int[ ] arr1 = new int[ 4];
arr1[0] = 45;
遍历数组:
使用for循环或者增强for循环即可。
数据访问越界问题
当访问下标大于等于数组容量,就会出现:java.lang.arrayIndexOutOfBoundException.
3. 从内存深入数组
在java语言中,数组也是一种类型,java语言要求数组元素类型是惟一的。
数组是一种引用数据类型,数组引用变量只是一个引用,数组元素和数组变量在内存中是分开的。
要访问图示中的数组元素,则程序中只能通过P[index]的形式实现。
看待一个数组,看把他分成两部分看,一部分是数组引用(数组变量);还有一部分就是运行在堆中的实际数组对象,通常无法直接访问,只有通过数组引用变量来访问。
4. 数组如何实现随机访问?
现在有一个数组:
int[] a = new int[10];
那么计算机会分配一个连续的内存空间1000~1039,其中该内存空间起始位置记为baseaddr=1000;
计算机会给数组中的每个元素分配一个地址,通过这个地址来访问元素,这个地址是通过一个寻址公式计算得出;
寻址公式:baseaddr + i * data_type_size = a[i]_addr;
第i个元素内存地址为:起始地址 + 元素下标 * 元素类型长度
数组支持随机访问,所以时间复杂度为:O(1)。
5. 为什么数组的插入、删除低效?
插入:
假设要往一个长度为n 的数组的k位置插入数据。以为数组内存空间是连续的,所谓插入前,要将k~n这部分元素依次向后挪一位。
最好时间复杂度:在最后一位插入,时间复杂度为:O(1).
最坏时间复杂度:在第一位插入,时间复杂度为:O(n).
因为插入的概率一样,所以平均时间复杂度为:O(n)。
在元素无序的条件下,如果在k位置插入m元素,可以把k位置原来的元素直接放到最后一位,然后把m放入k位置。所以在特定场景,这种插入方法时间复杂度将为O(1)
删除:
和插入类似,最好时间复杂度:O(1). 最坏时间复杂度为:O(n). 平均时间复杂度为:O(n)。
在某些特殊情况下,要删除一些元素,不需要将多次删除操作一起执行,而是把每次删除操作不是真正删除元素,而是把要删除的元素记录下来,当数据没有多余空间存储元素时,在触发一次真正的删除操作。(JVM标记垃圾清除算法的思想)
6. “打破”数组固定长度的局限
7. 与容器相比,数组更好的使用场景
容器如法存储基本类型,在自动装箱过程会有一定性能损耗,在很注重性能或希望使用基本类型时,可以选择数据;
在容量确定,并且对数据操作简单,也可以选择数组。
8. 为什么很多编程语言的数组都从0开始编号?
原因1:从数组内存模型来看,“下标”最确切的定义是“偏移”。
a[0]就是偏移为0的位置,a[k]就是偏移为k的位置,所以寻址公式为:
baseaddr + k * data_type_size = a[k]_addr;
但如果从1开始,那么寻址公式为;
baseaddr + (k - 1) * data_type_size = a[k]_addr;
对于CPU来说,需要多做一次减法指令。
原因2:历史原因。
C语言从0开始,所以后来的部分高级语言,模仿C从0开始,也是为了减少C程序员学习java的成本。