数组

大约 3 分钟

数组

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

  • 线性表，数据排成像一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。数组，链表，队列和栈等都是线性表结构；

    非线性表，如二叉树，堆，图，数据之间并不是简单的前后关系

  • 连续的内存空间和相同类型的数据，可以随机访问，但是删除插入数据，为了保证连续性，需要大量的数据搬移导致低效

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

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过寻址公式计算出该元素存储的内存地址:

a[i]_address = base_address + i * data_type_size

其中base_address是内存块的首地址，data_type_size是数组中每个元素的大小

插入操作

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

如果数组的数据是有序的，在某个位置插入一个新元素时，必须搬移；

如果数组中的数据是没有规律的（特定场景），为了避免大规模的数据搬移，可以直接将第k位的数据搬移到数组元素的最后，把新的元素直接放到k的位置，如

a,b,c,d,e  -> a,b,x,d,e,c

删除操作

如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)

在某些特殊场景下，并不一定非得追求数组中数据的连续性，将多次删除操作集中在一起执行提升效率，如先标记删除，当数组没有更多的空间存储数据时触发真正的删除操作（类似JVM的标记-清除）

需要注意数组越界，在Java中会抛出java.lang.ArrayIndexOutOfBoundsException

容器能否完全替代数组

ArrayList封装了很多数组的细节，支持动态扩容(1.5倍)，两者比较:

  • ArrayList无法存储基本类型，需要对应的拆箱和装箱，有性能损耗，

  • 如果数据大小已知，且操作简单，用不到ArraList的大部分方法，可以直接使用数组，

  • 如果是多维数组，使用数组更直观

为什么大多数编程语言中，数组要从0开始编号，而不是1

历史原因，和

a[k]_address = base_address + k * type_size

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

从1开始编号，每次随机访问数组元素都多一次减法运算，对于CPU来说，就是多了一次减法指令

今日诗词API