这节课主要讲了数组的概念及对应特点的影响，还跟 Java 的 ArrayList 做了比较。
概念
- 数据是一种线性表数据结构，所谓线性表，就是数据排成像一条线一样的数据结构。
- 这里数组用一组连续的内存空间，来存储相同类型的数据。
数组支持随机访问。这个特点也是因为它占有连续的内存空间。数组的寻址公式是 :
a[i]_address = base_address + i *data_type_size
当面试时，我们不应该说数组的查找时间复杂度是 O(1)，排序好的数组，用二分查找，时间复杂度是 O(logn)。正确的表述是，根据下标随机访问的时间复杂度是 O(1)。
但是也是因为这个原因，数组的插入和删除非常“低效”。为了保持连续性，需要做大量的数据迁移工作。
插入
如果数据是有序的，每次插入到数组的第 k 个位置，需要把 k~n 这部分数据都往后移以为，若是在每个位置插入元素的概率是一样的，那么平均时间复杂度是 (1+2+...n)/n=O(n)。
若数据是无序的，数组只是一个存储数据的集合，这种情况下，要把数据插入到第 k 个位置，可以尝试把第 k 个元素移到数组的最后面，把新元素插入到第 k 个位置，这样在特定场景下，插入一个元素到第 k 个位置时间复杂度可以降为 0。
删除
和插入一样，最好情况下时间复杂度是 O(1)，如果删除开头的数据，则是最坏情况时间复杂度 O(n)，平均情况下时间复杂度是 O(n)。
如果我们将多次删除操作集中在一起删除，就可以提高删除的效率，这也是 jvm 的标记清楚垃圾回收算法。
容器
ArrayList 相比数组，最大的优势就是将许多细节封装起来了，比如前面提到的数组插入、删除时需要搬移其他数据等。另外的优势就是自动扩容了。
但不是所有情况都需要用到 ArrayList。比如
- ArrayList 无法存储基本类型。自动封箱拆箱需要性能消耗。
- 有些操作较为简单，无需用到 ArrayList。
- 定义多维数组时，若是用 ArrayList 看起来不直观。
网友评论