数组

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

//基本结构
private int[] data;
//扩展
private int size;//数组的长度
private int index;//当前已经存的数据大小

优缺点

  • 随机存取，速度快，整体占用空间小（不像 [[2. 链表|链表]] 一样需要额外增加结点的空间）
  • 大小固定，不灵活，会有内存碎片
  • 插入和删除开销大（需要移动元素）

适合使用数组的场景

  1. 极端的性能要求：Java 中 ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
  2. 业务操作并不复杂的时候：如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
  3. 表示多维数组：用数组往往会更加直观。比如 Object[][] array；而用容器的话则需要这样定义：ArrayList<ArrayList<object>> array。

[!warning]+ 注意
对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

初始化同时也是一个需要注意的问题，因为数组的扩容往往意为着大量数据的搬移，所以为了避免这个问题出现，初始化数组就是一个良好的解决方案，如果开发者能够根据实际业务需求初始化合适的数组大小，就能极大程度的减少甚至避免数组的扩容。

数组起始下标为 0 的原因

  1. 数组名即为数组的首地址，且存储内容类型相同。——因此可根据固定公式计算地址（arr[n]=arr_head+n*type_size）。
  2. 数组由连续的内存空间组成。—— 因此可做到随机访问。
  3. 若从 1 开始，将会多做一次“-”操作，即 arr[n]=arr_head+(n-1)*type_size 对于最基本的数据类型来说，更注重性能，故使用 0 来作为起始下表。

数组的插入

public void insert(int loc, int n) {        //在loc位置，添加n，时间复杂度 O(n);
    if (index +1 <= size) {//判断数组是否越界
        for (int i = size - 1; i > loc; i--) {
            data[i] = data[i - 1];//把loc后的所有数据往后移一个位置
        }
        data[loc] = n;
        index++;
    }{
        //扩容
    }
}

数组的删除

public void delete(int loc) {    //删除loc位置的元素，O(n)
    for (int i = loc; i < size; i++) {
        if (i != size - 1) {//怕越界所以加一个判断 防止data[i+1]越界
            data[i] = data[i + 1];
        } else {
            data[i] = 0;            //默认为0 就是没存数据的
        }
    }
    index--;
}

数组的修改和查询

public void update(int loc, int n) {//修改，O(1)
    data[loc] = n;
}

public int get(int loc) {        //查询，O(1)
    return data[loc];
}

关于数组适合查找的误区
数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

二维数组

int[][] arr=new int[2][3];
//可以分解为两个连在一起的长度为3的一维数组
//寻址公式同样适用
//int[][] arr=new int[m][n];
//二维数组的寻址公式
//arr[j][k]=arr_address+(j*n+k)*type_size