1. 数组

1.  数组是一种线性数据结构。常见的的线性表结构有数组、链表、队列、栈 ，非线性表为树、图。
2.  用一组连续的内存空间来存储一组具有相同类型的数据。

2. 数组下标随机访问

　　查询效率高。

　　计算机随机访问数组中的某个元素时，通过下面的寻址公式计算元素存储的的内存地址；若下标以1开始，则要进行一次（i -1）操作。

// 元素内存地址 =  首地址 + 偏移量 * 数组类型的长度                     a[i]_address = base_address + i * data_type_size

　　数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。

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

3. 插入和删除

　　为了保证数组的连续性，需要做大量的数据搬移工作。

　　1） 插入：从最好O(1) 最坏O(n) 平均O(n)；

　　2） 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把新的元素，插入到第k个位置，此处复杂度为O(1)。

　　3） 删除：从最好O(1) 最坏O(n) 平均O(n)；

　　4） 多次删除集中在一起，提高删除效率。 记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除                  垃圾回收算法。

4. 容器和数组

　　相比于数组，Java中的ArrayList封装了数组的很多操作，并支持动态扩容。但是一旦超过存储容量，扩容时比较耗内存，因为涉及到内存申请和数据搬移。

4.1 数组适合的场景：　　

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

　　2） 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组；

　　3） 表示多维数组时，数组往往更加直观；

　　4） 业务开发使用容器即可。若涉及底层开发，如网络框架，性能优化等，则最好选择数组。

5.  解答开篇问题

1. 从偏移角度理解a[0] 0为偏移量，如果从1计数，会多出K-1。增加cpu负担。
2. 也有一定的历史原因，C 语言设计者用 0 开始计数数组下标，后面语言延续此设计。