21 / 02 / 17

Java 数据结构丨数组

基本概念

数组是最为简单、最为常用的数据结构。
数组对应的英语名称是 Array，是有限个相同类型的变量所组成的有序集合；数组中的每一个变量被称为元素。
数组是一种线性表数据结构（除了数组，还有链表、队列、栈等）；与其对立的是非线性表（二叉树、堆、图等）。数组的下标从 0 开始，而不是 1；直到 array.length - 1 为止。
数组里边存放的数据类型要一致，可以基本数据类型，也可以是引用数据类型，但是唯一的标准就是相同的类型。
打印 Java 数组用的是 ArrayName.toString() 而不是 ArrayName 。

// myArray1仅仅是一个地址引用

int[] myArray1 = {3, 6, 7, 9, 5};

// 直接输出的是内存地址

System.out.println(myArray1);

// myArray1.toString()才是真正的数组值

System.out.println(Arrays.toString(myArray1));

基本操作

读取

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

System.out.println(array[index]);
插入
- 尾部插入，这是最简单的情况，直接把要插入的元素放在数组尾部的空闲位置即可，不需要移动数据。
- 中间插入，这种情况稍微复杂，需要移动数据：假设某有序数组的长度为 N，要将一个新数据插入到该数组的第 K 个位置，那么需要将 K~N 这部分的元素都顺序地往后挪一位，以腾出第 K 个位置给新数据。
  
  如果数组中存储的数据并没有任何规律，数组只是被当做一个存储数据的集合，实现将新数据插入到第 K 个位置，为了避免大规模的数据搬移，可以取巧：直接将原本第 K 位的数据移到数组元素的最后，再把新数据直接放入第 K 个位置。
- 超范围插入，数组的长度是不变的，一旦数组完成初始化后，它的长度就固定下来了，在内存中占有的空间也就固定了，即使里面的数据被清空了，占有的空间还是保留下来了，依然是属于数组的，当然长度依旧是不变的。想要向空间已满的数组插入一个新数据，这就要涉及到数组的扩容了。
```
/**

  * @param index 新元素插入的位置

  * @param element 插入的新元素

  * @throws Exception 超出边界异常

  */

public void insert(int index, int element) throws Exception {

    // 判断访问下标是否超出范围

    if(index < 0 || index > size){

        throw new IndexOutOfBoundsException("超出数组实际元素范围！");

    }

    // 从右往左循环，将元素逐个向右移动1位

    for(int i = size-1; i >= index; i--){

        array[i+1] = array[i];

    }

    // 腾出的位置放入新元素

    array[index] = element;

    size++;

}
```

删除

和插入操作类似，最好的情况是删除数组末尾的数据；最坏的情况是删除开头的数据。

若要删除第 K 个位置的数据，为了内存的连续性，也需要搬移数据。前提与插入的取巧操作一样，删除第 K 个位置的数据，也可以取巧：可以把数组的最后一个元素复制到第 K 个位置，再删除最后一个元素。和插入操作相反，如果要删除的元素位于数组中间，其后的元素都需要向前移动 1 位。

/**
   * @param index 删除的位置
   * @return 返回删除的元素
   * @throws Exception 超出边界异常
   */
  public int delete(int index) throws Exception {
      // 判断访问下标是否超出范围
      if(index < 0 || index >= size){
          throw new IndexOutOfBoundsException("超出数组实际元素范围！");
      }
      int deletedElement = array[index];
      // 从左往右循环，将元素逐个向左移动1位
      for(int i=index; i < size-1; i++){
          array[i] = array[i+1];
      }
      size--;
      return deletedElement;
  }

常用 API

binarySearch(Object[] array, Object key) ：从数组中查询指定位置的元素，或者查询某元素在指定数组中的位置，如果要搜索的元素在指定的范围内，则返回搜索键的索引。
compare() ：比较两个数的大小，如果二者相等返回 0，如果前者大于后者，返回 1；反之返回 -1。
Arrays.equals(arrayA, arrayB) ：比较数组元素的个数和对应位置的元素是否相等，返回布尔型结果。
Arrays.fill(array, value) ：在数组指定位置进行数值填充，只能使用同一个数值进行填充。
Arrays.copyOf(dataType[] srcArray,int length) ：数组复制。

优劣

数组具有非常高效的随机访问能力，只要知道下标，就可以用常量时间找到相对应的元素。由于数组元素连续紧密地存储在内存中，插入、删除元素操作都会导致大量元素被迫移动，影响效率。

数组适合的是 读取操作多、写操作少 的场景。数组有一个缺点，就是一旦声明，就不能改变容量，这个也是其使用频率不高的原因。

参考

Arrays.copyOf()&System.arraycopy()_arrays.copyof和system.arraycopy-CSDN博客

Arrays (Java SE 9 & JDK 9 ) ( oracle.com )

Data Structure

Java