文章为极客时间《数据结构与算法之美》的学习笔记。
什么是数组？
数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
数组如何实现随机访问数组元素？
计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要访问数中的某个元素时，它首先会通过下面的寻址公式，计算出该元素存储的内存地址：
a[i]_address = base_address + i * data_type_size
数组与链表的区别？
链表适合插入、删除，时间复杂度是O(1)；数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。
容器(List)和数组(Array)的区别：
List底层通过数组实现的，List将很多数组操作的细节封装起来，比如数组的插入和删除，同时还支持动态扩容。
而数组在定义的时候需要预先指定大小，因为需要分配连续的内存空间。
容器和数组的使用场景：
- 在Java中，ArrayList无法存储基本类型，(在编译器中声明会直接报错)，比如int和long，需要封装为Integer、Long类，而装箱和拆箱具有一定的性能消耗，如果特别关注性能，或者希望使用基本类型，就可以选用数组
- 如果数据大小事先已知，并且对数据的操作非常简单，用不到集合提供的大部分方法，也可以直接使用数组
- 使用多维数组时，用数组会更加直观
注：Java中集合不能存储基本类型的原因是Java的泛型是靠类型擦除实现的，是指把某个具体的泛型引用在编译期完成类型检查后，擦除成了Object而丢失了它运行时所赋予的类型信息。所以类型参数都必须是引用类型不然没法确定占据空间的大小，比如Collection里面的ArrayList<T>，对于int这种基本类型就没法放，要想用ArrayList就得通过Integer包装一下。
ArrayList的源码，存储数据是声明了Object类型的数组：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
为什么大多数编程语言中，数组要从0开始编号，而不是1开始编号？
从数组存储的内存模型上来看，下标最确切的定义应该是偏移，比如数组a，a[0]就是偏移为0的位置，也就是首地址，a[k]就表示偏移k个type_size的位置，所以计算a[k]的内存地址只需要用到上面提到的公式：
a[k]_address = base_address + k * data_type_size
但是如果数组从1开始计数，那计算数组元素a[k]的内存地址就会变为：
a[k]_address = base_address + (k-1) * data_type_size
从1开始编号，每次随机访问数组元素都多了一次减法运算，选择从0开始编号，而不是1开始可以尽可能的优化访问元素效率。
C语言设计者用0开始计算数组下标，之后的java等高级语言都效仿了C语言，可能是为了减少学习成本，继续沿用了从0开始计数的习惯。
