数组和链表的区别:

链表适合删除、插入,时间复杂度是O(1),数组适合查找,查找特定的下标的数组元素时间复杂度是O(1)。
数组是一块连续分配的存储空间,通过下标查找数组元素的原理是:i*块大小 找到数组元素的内存地址;读取数组;

数组插入数据:

如果是在最后面插入,时间复杂度是O(1),如果是在第一个位置插入,时间复杂度是O(n);换一种方式,如果把要插入的第N个位置的元素取出,放到最后面;新元素插入到原来元素的位置,时间复杂度是O(1)。

数组删除数据:

如果删除的是末尾数组,时间复杂度是O(1),如果删除的是第一个位置的数据,时间复杂度是O(n)。平均时间复杂度是:O(n)
删除多个元素的时候,可以先标记为这些元素已经被删除,但是不真正删除。避免每删除一个元素,都要对后面的元素进行移动。当数组没有更多存储空间的时候,再触发执行一次真正的删除操作。减少数据被删除导致的迁移。
JVM 垃圾回收机制的核心思想就是这样的。

数组下标为什么是从0开始

下标指的是“偏移量”,0代表偏移量为0的内存地址。所以,计算a[k]的内存地址只需要用这个公式:

a[k]_address = base_address + k * type_size

但是,如果我们从1开始,那么公式会变为:

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

那么每次计算的复杂度都多了一次运算,对计算机来说是没有必要的。
所以数组是从0的下标开始的。

二维数组的内存地址怎么计算?

对于 mn 的数组,如果要找到a[i][j]的地址,那么计算公式为:
`a[i][j] = base_address + (n
i+j)type_size`
可以这么理解,a[i][j]是第I行J列的数据,那么偏移量是数组每列的数量n
i,再加上当前行的j,就是这个数组下标的内存地址了。

数组空间不足怎么操作(动态扩容)?

申请一块新的大于当前数组大小的空间,将原数据拷贝进去,并删除原来的数组空间。

总结

数组用一块连续的内存空间,支持通过下标随机访问,查询高效。但删除和插入时间复杂度较高,平均时间复杂度是O(n)。