数组

数组: 用一组连续的内存空间、存储一组具有相同数据类型的线性表数据结构

1.线性表: 数据只有前、后两个方向. 链表、队列、桟也是线性结构
2.连续空间、数据类型相同: 使得数组可以随机访问、但: 插入、删除数据的效率就低很多、需要数据重排

插入和删除

1.插入
  1) 末尾插入、无需移动元素、复杂度 O(1)
  2) 头部插入、搬移全部元素、复杂度 O(n)
  每个位置插入的概率相同、平均复杂度为 (1+2+3+...n)/n = O(n)
 
  若数组有序、只需要搬移k之后的数据
  若数组无序、且不要求有序、将k位置的元素直接搬移到最后、只需要一次搬移 O(1)
  
2.删除
  1) 与插入类似、最好O(1) 最坏O(n) 平均O(n)
  2) 删除多(m)个元素时、可先标记删除(只标记)、后一次性删除、节省m*O(n)次操作
     JVM的标记清除算法的核心

容器能否代替数组 ?

1. arrayList 将数组操作的细节封装. eg. 数据搬移
2. arrayList 支持动态扩容、默认扩容是1.5 
   扩容涉及到内存申请和数据搬移、比较耗时、若知道数据存储大小时、最好指定大小
   
 1. 容器无法存储基础类型、eg. int, long, 需要封装为 Integer、Long 而自动装箱则有部分性能损耗
 2. 若数据大小已知、且操作特别简单、可直接使用数组
 所以、对业务开发基本上直接使用容器就好、省力、不易出错、丢失的性能可以不太关注、不影响整体性能
 对底层开发、性能要做到极致、数组就优于容器成为首选
 

为什么大部分编程语言中、数组从0开始编号

下标确切定义是: 偏移offset、
1.使用a表示首地址、a[0]就是偏移为0的位置、即首地址、a[k]表示第k个type_size的地址
  a[k]_addr = base_addr + k*type_size
2.若使用1开始计数、则
  a[k]_addr = base_addr + (k-1)*type_size 
 从1开始编号、对于CPU来说、就是多了一次减法运算