数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据
线性表
- 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向
- 连续的内存空间和相同类型的数据
正是因为这两个限制，让他具有了的特性，但随之带来的是数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。
那是如何做到的随机访问的呢
前置知识：
当向计算机申请内存时，不同类型都有 data_type_size，如 int 类型数据就为 4 个字节。
计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：
数组
例：内存首地址 base_address = 1000，访问 a[1] = 1000 + 1 * 4;
一维数组寻址公式
// 下标为 i 的数组元素的地址 = 首地址 + i * 数据类型大小
a[i]_address = base_address + i * data_type_size
二维数组寻址公式
// 对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：
address = base_address + ( i * n + j) * type_size
ps: 谁规定是4个字节的，如果存的是 string 每个元素大小不同，这时要怎么寻址呢？
数组和链表的区别
- 链表适合插入、删除，时间复杂度 O(1)；
- 数组适合查找，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1);
数组的一些淫巧
数组插入、删除等操作就不过多啰嗦了！
在数组第 k 个位置插入数据
- 如果是有序，就是把数据插入，后面的数据进行搬移。
- 如果是无序，就可以偷个懒，避免大规模数据搬移，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。
总结
数组可以说是最基础、最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。
网友评论