一学一记：数组结构

¶一学一记：数组

¶概述:

数组是一种比较常见的基础数据结构，存储相同的数据类型，支持通过下标(index)进行随机访问，也是一种线性表结构，存储数据的是一块内存连续的空间。

¶概念解释:

线性表 : 数据最多只具备向前向后两个方向的，可以想到链表，队列也是一样的结构
随机访问实现：
- 因为数据在内存中需要的是一块连续的内存空间，而且数据中存储着相同的数据类型，这意味着每一个数据的在内存中的长度都是一致的，假设:
  - int[] a= new int[10] , 在计算机中分配到的内存空间如下所示 :
  - 将1000作为这个数组的起始地址(base_address),int类型长度为4字节(data_size),假设我们要查找a[5]位置的元素，计算方式就是:
  - $$
    a[5] Address = baseAddress + 5 * dataSize = 1000 + 20 = 1020
    $$
  - 数组在内存空间寻址公式就是这样，从基地址出发，将需要计算的偏移量乘以数据类型长度，得到该偏移量下的内存地址，即确定了元素在内存中的位置
数组的缺点：
- 低效的插入，删除 ：
  - 根据数据的存储特性，为了维护数组内存空间的物理连续性，当从数组中删除一个元素时，需要将该元素之后的元素都向前移动一位；在这种情况下，如果是进行头节点的删除，需要将剩下的所有元素位置都进行一次移动，在数量较大时显得很低效。
  - 插入—可优化场景：考虑到之前了解到的最好和最坏时间复杂度，如果是仅作为数据存储的无序数组，在进行数据的插入时，可以不进行数据的移动，而是通过将插入数据直接替换该索引位置数据，将被替换数据插入到尾部降低整体的操作时间复杂度:
  - $$
    往数组a的i位置插入X，temp = a[i]; a[i] = X ;a[n] = temp
    $$
  - 当然了这是假设数组有剩余空间的情况下可以直接这么处理，如果没有剩余空间还是得先进行整体数据的移动移动，在插入数据，ArrayList 的扩容就是基于这种方式实现的
  - 删除—可优化场景：数组的删除操作一定会导致内存空间的不连续，因此在没有要求每次删除都必须马上将数组空间空闲出来的情况下，可以对需要删除的数据进行标记，不触发真正的删除；等到数组空间不足，需要清理数据的时候再一次性将需要删除的数据清除，进行一次数据的移动，大大节省了操作时间，这种先将数据标记，然后进行数据清理的思路，和JVM的标记-回收算法类似。
数组的起始下标为何从0开始？
- 从合理性性的角度来说，根据我们刚才使用的数组内存寻址公式: bas_address + index * data_size ,数组中第一个元素的位置就是 base_address ,如果 index 从1开始，意味着这个计算公式要变成 base_address + (index-1) * data_size ，增加了一次运算操作，这次操作是可以避免的，以提高效率和节省CPU资源。

二维数组的寻址公式:

1
2
3

int[m][n] a; 
a[i][j] = base_adddress + (i*n + j)*data_size;
// 即定位二维数组的某个数组的元素地址，需要加上该数组之前的内存空间长度，再计算自身索引条件下查找元素的内存地址

小结：

数组是一种支持随机访问的线性表结构，它在连续的内存空间中存储着相同类型的数据
一维数组的寻址公式为 : 基地址 + 偏移量*数据类型长度
数组的插入，删除元素操作效率较低，在不考虑数组数据有序性的前提下：
- 插入:往数组i位置插入元素X，可以将a[i]元素放置数组尾部，X放置在a[i]位置，这样操作的时间复杂的降低为O(1)
- 删除:如果数组空间充足，对于需要删除的数据可以先进行删除状态标记，等到需要腾出数据空间的时候，再对这些数据进行一次性删除，节省了多次删除的数据移动操作，提高了执行效率