什么是数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
数组的缺点
因为是线性表并且是连续的内存空间 如果想要在数据中增删数据 为了保证数据的一致性 必须要移动内存空间
数组是如何实现根据下标随机访问数组元素
int a = new int[10] 定义一个长度为10的数组 假定给其分配的内存空间为1000-1039
计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据
寻址公式
a[i]_address = base_address + i * data_type_size目的地址 首地址 数组元素的类型大小比如在此刻int为4个字节 求得目的地址为1004
什么是线性表
数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向
常见的线性表
- 数组
- 链表
- 栈 先进后出
- 队列 先进先出
什么是非线性表
常见的非线性表
- 二叉树
- 堆
- 图
如何实现随机访问
- 线性表
-
低效的插入与删除
插入
假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。
数组是连续数据
- 如果插入的位置为末尾 则不需要移动数据 则O(1)
- 如果在开头插入 则每位都需要移动所以平均情况时间复杂度为 (1+2+…n)/n=O(n)。
- 数组是不连续数据
直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。 复杂度就会降为O(1)
删除
数组是连续数据
- 如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。
- 删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)
- 数组是不连续数据
- 数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。
为了避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
警惕数组的访问越界问题
为什么会发生数组访问越界问题
在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据我们前面讲的数组寻址公式，a[3]也会被定位到某块不属于数组的内存地址上而在Java中会对数据进行越界检测 java.lang.ArrayIndexOutOfBoundsException。
容器能否完全替代数组？
ArrayList的优点
若有收获，就点个赞吧
0 人点赞
