注：此专栏内容主要参考极客时间-数据结构与算法之美

数组

1. 概念
   数组是一种线性表结构，它用一组连续的空间，存储具有相同类型的数据；

2. 线性表
   线性表即线一样的数据结构，数组、链表、栈、队列都属于线性表；
   
   

3. 查询快
   因为数组定义是连续的、相同的元素，所以数组的特点是通过下标查找元素较快，插入、删除较慢；

   元素a[i]，内存地址计算公式

a[i]_address = base_address + i * data_type_size

data_type_size ：数组中每个元素的大小。

根据下标随机访问的时间复杂度是O(1)；

• 插入、删除 慢

• 如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为 O(1)。

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

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

• 在某些特殊场景下，我们并不一定非得追求数组中数据的连续性，即连续删除多次后，再统一挪动数组元素，“以空间换时间”，这也是JVM-“标记清除垃圾回收算法”的特点；

• 数组操作需要警惕数组越界

• ArrayList（容器）与数组对比

• 将很多数据操作的细节进行了封装

• 支持动态扩容

• 创建ArrayList的时候先指定数据大小

• ArrayList不支持基本数据类型，元素如果是基本数据类型，需要转换成包装类处理

• 多维数组操作（比如二维），ArrayList写法就是ArrayList<ArrayList > array，很不好看

7.为什么数组从0开始，不是从1开始

• 从0开始，元素a[i]，内存地址计算公式

a[i]_address = base_address + i * data_type_size

• 从1开始，元素a[i]，内存地址计算公式

a[i]_address = base_address + (i -1)* data_type_size

从 1 开始编号，每次随机访问数组元素都多了一次减法运
算，对于 CPU 来说，就是多了一次减法指令。
数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。