Java笔记 ·

数据结构01-数组

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据

  • 因为线性表连续的内存空间和相同类型的数据这两个特性,数组的随机访问速度快。
  • 也因此,具有低效的“插入”和“删除”

动态数组,是指数组的容量能动态增长的数组,对于Java而言,Collection集合中提供了ArrayList和Vector。

插入操作

若有一元素想往int[n]的第k个位置插入数据,需要将k~n位置的元素顺序往后移一位。
- 最好时间复杂度O(1),插在末尾不需要移动数据时
- 最坏时间复杂度O(n),插在开头,所有数据均需要移动
- 平均时间复杂度O(n),根据(1+2+3+...+n)n = O(n)

当为无序数组时,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放到第K位上,此时时间复杂度依旧为O(1)。

删除操作

和插入类似:

  • 最好情况时间复杂度为 O(1),删除数组末尾的数据时。
  • 最坏情况时间复杂度为 O(n),删除开头的数据时。
  • 平均情况时间复杂度也为 O(n),同插入操作的公式。

某些情况下,为了避免数据会被搬移多次,我们可以结合JVM 标记清除垃圾回收算法的核心思想,先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据,只是记录数据已经被删除。当数组没有更多空间存储数据时,我们再触发执行一次真正的删除操作,这样就大大减少了删除操作导致的数据搬移。

链表与数组的区别:

  • 链表适合插入、删除,时间复杂度 O(1);
  • 数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

容器(ArrayList)与数组的适用场景

ArrayList将所有数组操作封装起来,且支持动态扩容,每当空间不够时,自动扩容空间1.5倍。

  • ArrayList 无法存储基本类型,比如 int、long,需要封装为 Integer、Long 类,而 Autoboxing、Unboxing 则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本类型,就可以选用数组。
  • 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。
  • 表示多维数组时,用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList<ArrayList> any

数组下标从0开始

int[] a = {10,20,30,40,50} 的存储示例如下:

计算机会给每个内存单元分配一个地址,计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时,它会首先通过下面的寻址公式,计算出该元素存储的内存地址:

a[i]_address = base_address + i * data_type_size

其中,data_type_size是数组中每个元素的大小。

假设计算机为上面的数组int[] a分配了一块连续的内存空间1000~1019,首地址为base_address = 1000,因为是int类型,这里的data_type_size为4个字节,其内存空间分配如图:

如果数组下标从1开始,计算公式将成为如下:

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

从 1 开始编号,每次随机访问数组元素都多了一次减法运算,对于 CPU 来说,就是多了一次减法指令。但更多的可能是由于历史原因,C的设计者使用了0作为下标开始,Java沿用了该设计。

结语

这里主要从数据结构角度介绍了一下数组,其它的数组知识点可以看下面两篇文章:

Java漫谈-数组

[转]Java中的数组是对象吗?

本文参考资料

数据结构与算法之美

参与评论