这节课主要讲了数组的概念及对应特点的影响，还跟 Java 的 ArrayList 做了比较。

抛出一个问题：为什么数组要从0开始编号，而不是从1开始？（从1开始不是更符合人类的思维习惯？）

一、 数组如何实现随机访问

数组是什么？

定义：数组（Array）是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据。

定义里有几个关键字，解析一下：

1）线性表（Linear List）：

       ①什么是线性表？

            顾名思义，线性表就是数据排成想一条线一样的结构。每个线性表上的数据最多只有前后两个方向。

           除了数组，链表、队列、栈等也是线性表结构。

        ②非线性表：数据之间并不是简单的前后关系。

            非线性表：如二叉树树、图等。

线性表

非线性表

2） 连续的内存空间、相同的数据

        因为以上两种限制，数组才有了"随机访问"的特性。但是也因为这样子，让数组的很多操作变得非常低效。比如说：对数组进行删除、插入一个数据，为了保证连续性，就要做大量的数据搬移工作。

a) 数组如何实现下标随机访问。  

        数组的寻址公式是 :  

        a[i]_address = base_address + i * data_type_size

        其中data_type_size表示数组中每个元素的大小。

b) 纠正数组和链表的错误认识。

当面试时，我们不应该说数组的查找时间复杂度是 O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。

正确表述：数组支持随机访问，根据下标随机访问的时间复杂度为O（1）。

二、低效的插入和删除

（1）插入

        最好情况下时间复杂度是 O(1)，如果插入开头的数据，则是最坏情况时间复杂度 O(n)，平均情况下时间复杂度是 O(n)。

        如果数据是有序的，每次插入到数组的第 k 个位置，需要把 k~n 这部分数据都往后移以为，若是在每个位置插入元素的概率是一样的，那么平均时间复杂度是 (1+2+...n)/n=O(n)。

        若数据是无序的，数组只是一个存储数据的集合，这种情况下，要把数据插入到第 k 个位置，可以尝试把第 k 个元素移到数组的最后面，把新元素插入到第 k 个位置，这样在特定场景下，插入一个元素到第 k 个位置时间复杂度可以降为 O（1）。

插入

（2）删除

        和插入一样，最好情况下时间复杂度是 O(1)，如果删除开头的数据，则是最坏情况时间复杂度 O(n)，平均情况下时间复杂度是 O(n)。

        我们可以先记录下已经删除的数据。每次删除数据并不是真正地删除操作，只是记录数据已经被删除。当数组没有更多控件存储数据时，我们再触发一次真正的删除操作，这样就大大减少操作导致的数据搬移。

        如果我们将多次删除操作集中在一起删除，就可以提高删除的效率，这也是 jvm 的标记清除垃圾回收算法的核心思想。

三、警惕数组的访问越界问题

四、容器能否完全替代数组

        相比于数字，java中的ArrayList封装了数组的很多操作，并支持动态扩容。一旦超过存储容量，扩容时比较耗内存，因为涉及到内存申请和数据搬移。所以，如果知道容量大小，指定ArrayList的大小就会好很多。

数组适合的场景：

1） Java ArrayList 的使用涉及装箱拆箱，有一定的性能损耗，如果特别关注性能，可以考虑数组。

2） 若数据大小事先已知，并且涉及的数据操作非常简单，用不到ArrayList提供的大部分方法，可以选用数组。

3） 当表示多维数组时，选用数组往往更加直观。

4）底层开发，如网络框架，性能优化。选择数组。

那什么时候使用ArrayList?

  答：   一般来讲，对于业务开发，直接使用容器ArrayList就够了，省事省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。

五、 解答开篇问题：

为什么大多数变成语言中，数组要从0开始编号，而不是从1开始呢？

1）从偏移角度理解

        从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用a来表示数组的首地址，a[0] 就是偏移量为 0 的位置，也就是首地址， a[k] 就表示偏移k个type_size的位置，所以计算a[k] 的内存地址只需要用这个公式：

        a[k]_address = base_address + k * type_size

        但是，如果数组从1开始计数，那我们计算数组元素a[k] 的内存地址就会变为：

        a[k]_address = base_address + (k-1)*type_size

对比两个公式，可以发现，从1开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU来说，就多了一次减法指令。对CPU来说，就是多了一次减法指令。为了效率优化到极致，减少一次减法操作，数组选择了从0开始编号，而不是从1开始。

2） 历史原因

        C语言设计用0开始计数数组下标，之后的Java、JavaScript等高级语言都效仿了C语言，或者说，为了在一定程度上减少C语言程序员学习Java的学习成本，因此继续沿用了从0开始计数的习惯。实际上，很多语言也并不是从0开始计数的，比如Matlab。甚至还有一些语言支持负数下标，比如说Python.