数据结构基础02——线性数据结构之数组

定义:
ps:但凡有一点编程知识也不会不知道这是什么,所以可以略过下面一段- -!
所谓数组,是有序的元素序列。若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。

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

关键词:
线性表:见线性表描述

连续存储空间:因为存储空间是连续的,所以数组有着高效的随机访问特性。和低效的随机插入修改
why?(数组的元素是如何读取的)

读取操作
假设我们定义数组arr = new int[100];
其中arr[0]占用内存地址0x76543210到0x76543213来保存。
因为内存地址是连续的,且每个元素类型相同(占用空间相同)
所以当我们需要知道下标n的数据时。只需要n乘以每个单个类型所需空间 + arr[0]的地址即可。而不需要像链表一样一个个的去遍历找到对应的值
如图:

image.png

添加操作:
假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。。如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为 O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是 O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。如果数组中的数据是有序的,我们在某个位置插入一个新的元素时,就必须按照刚才的方法搬移 k 之后的数据。但是,如果数组中存储的数据并没有任何规律,数组只是被当作一个存储数据的集合。在这种情况下,如果要将某个数据插入到第 k 个位置,为了避免大规模的数据搬移,我们还有一个简单的办法就是,直接将第 k 位的数据搬移到数组元素的最后,把新的元素直接放入第 k 个位置。

删除操作
跟插入数据类似,如果我们要删除第 k 个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为 O(1);如果删除开头的数据,则最坏情况时间复杂度为 O(n);平均情况时间复杂度也为 O(n)。
优化:这里可以把删除操作集中处理,如删除下标元素n时,不是真的删除而是给n添加一个标记,到必要时再一次性删除所有标记元素(想想标记清除算法)

内存溢出,越界
在有的内存可以自由访问的语言中(如:C)。基于上面所说的内存访问原则,如果访问下标超出数组大小,就会读取到下一个空间。在Java中则会抛出下标越界ArrayIndexOutOfBoundsException

特性总结:一般而言,数组的随机访问速度非常快(O(1)),但是添加删除都是O(n)的时间复杂度。

但是:
数组的访问或遍历速度一定比链表快吗?
NO,注意是随机访问

Java中数组的插入速度一定比链表慢吗?
NO,且不说是最后一个。插入的前提是你得先找到插到哪儿。另外基于System.arrayCopy等实现,在小规模数据时链表确实比数组快,但是大规模就不一定了,感兴趣的可以自己去测试,不要人云亦云 - -

直接用容器取代数组可以吗?
NO,在java中如ArrayList对数组有很好的封装,但是首先ArrayList没办法存储基本数据类型,其次ArrayList的自动扩容和初始大小(当然也可以指定)并不靠谱如:一次扩容1.5倍。在数据大小基本已知情况下不划算。最后对于多维数组(表示图或矩阵等)时,数组比ArrayList直观得多
(int[1][2] VS ArrayList<ArrayList>)

如果已知修改少查找多的数据用数组需要考虑什么吗?
连续内存空间的占用

更新时间:2020-01-22 09:58:26

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础02线性数据结构之数组
最后更新:2020-01-22 09:58:26

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×