你真的认识数组吗?

你真的认识数组吗?

困而学,学而知

站在巨人的肩膀上

在日常的开发中,数组可以说是用得最多的数据结构,可以说每天写的业务代码无处不是数组。按什么是数组,如果是C语言开发的同学会说int[]int[][]是数组,如果是Java语言开发的同学会说ArrayList(当然了Java语言中也会有int[]这种结构,只是基本上还是会用ArrayList)。

那什么是数组?引用《数据结构和算法之美》:数组(Array)是一种线性表数据结构。他用一组连续的存储空间,来存储一组具有想同类型的数据

还有其他的线性表:链表、队列、栈

非线性表:二叉树、堆、图等

数组-连续的内存空间

请注意上面所说的连续的存储空间,正因为数组使用了连续的存储空间,所以才保证的数组数据的随机访问。但是怎么建立起这种因果关系的?这里我们先创建一个长度为10的数组:int[] arr = new int[10]。计算机会为这个arr在内存中分配一块连续的内存空间1000~1039(Java中int占4个字节,32个bit), 内存的首地址是baseAddress=1000

数组的连续空间

如果现在要获取a[6]的值是多少,怎么做到呢?要获取a[6]的值,其实也就是要获取a[6]的地址是多少,因为数组是一段连续的内存空间,我们主要知道首地址是多少就可以了,通过下面的公式就可以知道a[6]的地址了

a[6]_address = 1000 + 6 * 4 
 // 这里4是int的字节数,因为每个数据类型的字节数不一样,我们直接用data_type_size表表示
 // 通过上面的公式,我们可以推导出一个更通用的公式
a[i]_address = baseAddress + i * data_type_size

数组的插入和删除

上面说了数组是一个存储在一个连续的内存空间中,其实也可以理解为数组是一个空间有序的。既然是空间有序的,那么当数组中的数据被删除或者有新数据插入到数组怎么办?怎么保证数组在空间上面是有序的。

插入

如果是在数组的末尾插入,数组已经是已经是有序的,不用移动已经存在的数据,这个时候的时间复杂度就是O(1)。但是如果在数组的开头插入数据,那么所有的数据都需要向后依次移动一位,那么最坏的时间复杂度就是O(n)。因为在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为(1+2+...+n)/n=O(n).

在讨论一种新的情况,如果数组中的数据是有序的,我们要在数组中的k的位置插入新的数据,我们就需要将k位之后的数据向后依次移动一位。但是如果数据中的数据是无序的,我们还可以特殊处理,将第k为的数据直接放到数组的末尾,然后将新数据插入到k位。

删除

删除的处理其实和插入差不多,如果要删除k位置上的元素,我们就需要将k之后的数据向前移动一位。数组的删除操作的平均时间复杂度也是O(n)

可以看到,数组在插入和删除的时候,其实是通过移动元素来保证数组在空间上的有序性。

数组和链表的区别?

数组适合查找操作,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)。不同的查找算法的时间复杂度是不一样的,比如说前面所说的二分查找的时间复杂度是O(logn)。

链表适合插入和删除操作,链表的插入和删除操作的时间复杂度是O(1)。

虽然链表的删除操作的时间复杂度是O(1),但是删除的条件的需要找到需要删除的节点,而这个查找的时间复杂度是O(n)

关于链表,后面可以再写一篇文章讲讲。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://baozi.fun/2019/09/28/you-dont-know-about-array

Buy me a cup of coffee ☕.