数组（数据结构）

优质博文：IT-BLOG-CN

一、简介

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

数组因具有连续的内存空间的特点，数据拥有非常高效率的“随机访问”，时间复杂度为O(1)。但因要保持这个连续的内存空间，导致数组在删除或插入操作的时非常低效。因为数组为了保持连续性，必然会涉及大量数据的迁移，这个是非常消耗时间的，平均时间复杂度为O(N)。

二、数组的随机访问

数组的随机访问是有个寻址公式的，上问中我们提到过数组是用一组连续的内存空间存储数据元素的，然而每个内存单元都有自己的地址(在计算机里面就是通过这个地址访问数据的)，又加上每个内存单元的大小都是一样的，这样就很容易得到一个公式了，如下所示：

a[i]_address = base_address + i * data_type_size

我们来简单解释一下上述公式，其中data_type_size表示数组中每个元素的大小，base_address表示内存块的首地址，i表示数组下标。

三、数组的基本操作

【1】创建数组

public class MyArray {      
    private int[] array;     
    // 数组大小     
    private int size;           
    public MyArray(int capacity) {         
        this.size = 0;         
        this.array = new int[capacity];     
    }      
}
1
2
3
4
5
6
7
8
9

【2】读取元素： 我们知道数组在内存中是连续存储的，所以根据上文的寻址公式可以知道，我们可以根据数组下标i快速定位到对应的元素。

int[] array={1,2,3,4,5,6}; 
System.out.println(array[1]);  // 输出的是2  因为数组的下标是从0开始的。
1
2

【3】更新元素： 我们可以根据数组下标快速查找到对应元素。那么同样道理，我们可以根据数组下标i快速更新元素，这中间涉及两个过程，首先就是找到数组下标i对应的数据元素A，然后将新的数据元素B赋值给A即完成更新。

int[] array={1,2,3,4,5,6}; 
System.out.println(array[1]);  // 输出的是2  
//更新数组下标为 1 的数组元素 
array[1]=7; 
System.out.println(array[1]); // 输出的是7
1
2
3
4
5

【3】插入元素：相比读取、更新操作，插入元素稍微复杂一些，分为以下两种情况：

尾部插入： 首先，我们看看尾部插入，这种情况很简单，在数组的最后新增一个新的元素，此时对于原数组来说没有任何影响，时间复杂度为0(1)。如下图所示：

中间插入： 如果在数组的中间位置插入元素的话，此时会对插入元素位置之后的元素产生影响，也就是这些数据需要向后依次挪动一个位置。如下图所示：

/**  
 * 插入元素
 * @param index  待插入的位置  
 * @param element 待插入的元素 
 */ 
public void insert(int index, int element){     
    if(index < 0 || index > size) {        
        throw new IndexOutOfBoundsException("超过数组容量 ! 插入失败！");      
    }     
    // 从左到右，将元素向右移动一位     
    for (int i = size-1; i > index; i--) {
        array[i+1] = array[i];
    }     
    // 此时index这个位置已经腾空了，可以放进入element     
    array[index]=element;     
    //数组中元素个数+1     
    size++; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

【4】删除元素： 删除元素和插入元素类似，如果我们删除第k个位置的数据，为了内存的连续性，同样会涉及数据的挪动。如下图所示：

/**  
 * 根据数组下标删除元素
 * @param index 数组下标 
 * @return  
 */ 
public int delete(int index) {     
    if (index < 0 || index > size) {         
        throw new IndexOutOfBoundsException("已经超过数组容量 ! 插入失败！");     
    }     
    int deleteElement = array[index];     // 从左到右，将元素向左移动一位     
    for (int i = index; i < size - 1; i++) {         
        array[i] = array[i + 1];     
    }     
    size--;     
    return deleteElement; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、数组扩容

因为数组的长度在创建的时候已经确定了，当插入元素的时候如果数组已经满了，是没办法插入成功的。这个时候就要考虑数组扩容的问题了，那么该如何实现扩容呢?

其实我们可以这样，比如此时的数组是A, A已经满了，我们再创建一个数组B且数组长度是A的2倍，然后我们将数组A的元素全部放到数组B中，这样就完成了数组扩容了。

/** 数组扩容为原数组的二倍 **/ 
public void resize(){  
    int[] newArray = new int[array.length * 2];  
    System.arraycopy(array, 0, newArray, 0, array.length);  // 把从索引0（第一个0）开始的array.length个数字复制到索引为0（第二个0）的位置上  
    array = newArray;
}
1
2
3
4
5
6