数组
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表就是数据排成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。常见的有数组、链表、队列、栈等线性表结构，如下图所示：
与之相对的是非线性表，如二叉树、堆、图等，因为数据之间并不是简单的前后关系，如下图所示：
连续的内存空间和相同类型的数据使得数组支持随机访问，但是也限制了数组的其它操作，如删除、插入数据，为了保持连续性，就需要做大量的数据搬移操作。
如何实现数组的随机访问
计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。其中base_address就是分配给数组的内存空间首地址，通常就是数组的名称，data_type_size代表数组中每个元素的大小。i作为下标实际上代表的是内存的偏移。
如果从0开始计数，计算地址公式如下：
$$ a[i]_{address} = base_{address} + i * data_{type size} $$
如果从1开始计数，计算公式如下：
$$ a[i]_{address} = base_{address} + (i - 1) * data_{type size} $$
对比可以看出，从1开始计数每次从数组取值都需要进行额外的一次减法运算，对于CPU来说，多了一次减法指令。更多的也可能是历史原因，C最初是从0开始计数，后面的Java和JavaScript都是从0开始，减少了C语言程序员学习其他语言的成本。但是，从0开始计数并不必须的，也有其他的语言如Matlab是从1开始计数，Python还支持负数下标。
注：数组支持随机访问，根据下标随机访问的时间复杂度是O(1).
低效的插入和删除
插入
插入操作：在数组k位置插入一个数据时，需要将k之后的数据搬移，最好时间复杂度O(1),最坏时间复杂度O(n)，平均时间复杂度为O(n);在某些情况下，可以将原本k位置的元素放到数据的最后位置，这样，在第k个位置插入一个元素的时间复杂度就会降低为O(1).
删除
当删除数组中的一个元素时，为了保持数据的连续性，同样需要搬移数据，不能出现空洞数据在数组中，最好时间复杂度O(1),最坏时间复杂度O(n)，平均时间复杂度为O(n).
在每次删除数据时，可以只是记录下被删除的元素下标，将需要删除的元素构成一个待删除集合，当数组没有更多空间存储数据时，再通过一次删除操作将待删除集合中的元素全部删除，减少了单个删除需要的大量数据搬移次数。这是JVM中标记清除垃圾回收算法的核心思想。
警惕数组的访问越界问题
在C语言中，数组越界是一种未决行为，并没有规定数组访问越界时编译器应该如何处理，因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就考虑不会报任何错误。
但是在Java中，会做越界检查。
容器能否完全替代数组
Java中的ArrayList、C++ STL中的Vector都是容器，它们的优点是将很多数组操作的细节封装了起来，最重要的是它们还支持动态扩容。
需要注意，动态扩容操作设计内存申请和数据搬移，是比较耗时的，所以，如果事先能够确定需要存储的数据大小，最好在创建ArrayList的是否事先指定数据大小。
容器 VS 数组：
- Java ArrayList无法存储基本类型，比如int、long，需要封装为Integer、Long类，但是Autoboxing、Unboxing有一定的性能消耗，如果特别关注性能，或者希望希望使用基本类型，就选择数组
- 如果事先数据大小已知，对数据的操作非常简单，选择数组
- 多维数组使用数组会更加直观
总结就是，对于业务开发，选择容器能够省时省力，损耗的一点点性能不会影响到系统的整体性能。但是对于非常底层的开发，如网络框架的开发，性能的优化需要做到极致，优先选择数组。
注：本文是《数据结构与算法之美》的读书笔记，配套代码地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。
Note: Cover Picture