数组

数组

标签（空格分隔）： 数据结构和算法

理解数组

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

数组是如何实现根据下标随机访问数组元素

正是因为数组的特性：连续的内存空间和相同类型的数据

我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址
base_address 初始是 1000
data_type_size int类型 4字节


a[i]_address = base_address + i * data_type_size

数组的删除和插入

正是因为数组的特性：**连续的内存空间和相同类型的数据**
数组的删除和插入 需要保持连续的内存空间，需要**移动元素**

如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 O(n)


实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？我们继续来看例子。数组 a[10]中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素

为了避免 d，e，f，g，h这几个数据会被搬移三次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，**只是记录数据已经被删除**。**当数组没有更多空间存储数据时**，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移

为什么数组的下标要从0开始

计算内存地址：如果从0开始
a[k]_address = base_address + k * type_size


计算内存地址：如果从1开始
a[k]_address = base_address + (k-1)*type_size