数组

定义

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

特性

• 线性数据结构
• 连续的存储空间及相同的数据类型
  • 随机访问有优势
  • 插入和删除比较麻烦，需做大量的数据搬移操作

优化

• 插入
  • 当数组存储数据没有规律时，只是作为一个存储数据的集合，此时向第k位插入时，可以先将原来k位上的数据移到最后，将新数据添加到k位上
• 删除
  • 当数组有多次删除操作时，可以先将要删除的数据标记起来，然后再在一定的时机下进行真正的删除操作 (JVM标记清除垃圾回收算法的核心)

注意事项

• 数组访问越界
  • 在C语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。因此，很多计算机病毒正是利用代码中的数组越界可以访问到非法地址的漏洞来攻击系统，所以写代码的时候要时刻注意数组越界问题

动态数组ArrayList

• 使用ArrayList我们可以不用关心底层的扩容逻辑，当每次容量不够时，它都会自动将空间扩大为原有的1.5倍
  注：扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小
• 与数组之间的比较
  • ArrayList无法存储基本数据类型，需使用其包装类，而Autoboxing和unboxing则有一定的性能消耗，当比较关心性能时，优先使用数组
  • 如果数据大小事先已知，并且数据操作很简单的时候，优先使用数组
  • 表示多维数据的时候，用数组会更加直观

思考

为什么数组下标是从0开始？

• 当数组下标从1开始时，第k个数据的地址值的算法变成 a(k) = base_address + (k - 1) * type_size，这样CPU多了一次减法操作，从0开始可以避免这个问题而达到优化的目的