[[411318]]

本文轉(zhuǎn)載自微信公眾號(hào)「碼上Java」，作者碼上Java。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼上Java公眾號(hào)。

前言

數(shù)組是一種非?；A(chǔ)且重要的數(shù)據(jù)結(jié)構(gòu)，很多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)都是基于數(shù)組實(shí)現(xiàn)的。深入理解數(shù)據(jù)的存儲(chǔ)原理和特點(diǎn)，有利于我們?cè)趯?shí)際開發(fā)工作中，充分發(fā)揮數(shù)據(jù)的優(yōu)勢(shì)。

數(shù)據(jù)是什么

數(shù)組的定義：數(shù)組(Array)是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，存儲(chǔ)一組具有相同類型的數(shù)據(jù)。

在上面的定義中加黑的描述，我們可以發(fā)現(xiàn)數(shù)組的幾個(gè)特點(diǎn)，分別是：線性表、連續(xù)的內(nèi)存空間、相同類型的數(shù)據(jù)。如下圖所示：

數(shù)組因具有連續(xù)的內(nèi)存空間的特點(diǎn)，讓數(shù)據(jù)擁有非常高效率的“隨機(jī)訪問”，但也是因?yàn)橐３诌@個(gè)連續(xù)的內(nèi)存空間，導(dǎo)致數(shù)組在刪除或插入操作的時(shí)非常低效。因?yàn)閿?shù)組為了保持連續(xù)性，必然會(huì)涉及大量數(shù)據(jù)的搬移，這個(gè)是非常消耗時(shí)間的。

思考：這里你可能會(huì)有疑問：什么是連續(xù)的內(nèi)存空間?

首先，我們來說說內(nèi)存，內(nèi)存是由一個(gè)個(gè)連續(xù)的內(nèi)存單元組成的，每一個(gè)內(nèi)存單元都有自己的地址。在這些內(nèi)存單元中，有些被其他數(shù)據(jù)占用了，有些是空閑的。

然而數(shù)據(jù)中的每個(gè)元素，都存儲(chǔ)在小小的內(nèi)存單元中，并且元素之間緊密排列，既不能打亂元素的存儲(chǔ)順序，也不能跳過某個(gè)存儲(chǔ)單元進(jìn)行存儲(chǔ)。

數(shù)組的隨機(jī)訪問

數(shù)組的隨機(jī)訪問是有個(gè)尋址公式的，上問中我們提到過數(shù)組是用一組連續(xù)的內(nèi)存空間存儲(chǔ)數(shù)據(jù)元素的，然而每個(gè)內(nèi)存單元都有自己的地址(在計(jì)算機(jī)里面就是通過這個(gè)地址訪問數(shù)據(jù)的)，又加上每個(gè)內(nèi)存單元的大小都是一樣的，這樣就很容易得到一個(gè)公式了，如下所示：

a[i]_address=base_address+i*data_type_size 

我們來簡單解釋一下上述公式，其中data_type_size表示數(shù)組中每個(gè)元素的大小、base_address表示內(nèi)存塊的首地址、i 表示數(shù)組下標(biāo)。

數(shù)組的基本操作

在開始之前我們先創(chuàng)建一個(gè)數(shù)組類，來模擬數(shù)組操作時(shí)候的相關(guān)操作。代碼如下:

public class MyArray { 
 
    private int[] array; 
    // 數(shù)組大小 
    private int size; 
      
    public MyArray(int capacity) { 
        this.size = 0; 
        this.array = new int[capacity]; 
    } 
     
} 

1. 讀取元素

我們知道數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的，所以根據(jù)上文的尋址公式可以知道，我們可以根據(jù)數(shù)組下標(biāo) i 快速定位到對(duì)應(yīng)的元素。

簡單舉例，代碼如下：

int[] array={1,2,3,4,5,6}; 
System.out.println(array[1]); // 輸出的是2  因?yàn)閿?shù)組的下標(biāo)是從0開始的。 

2. 更新元素

我們可以根據(jù)數(shù)組下標(biāo)快速查找到對(duì)應(yīng)元素。那么同樣道理，我們可以根據(jù)數(shù)組下標(biāo) i 快速更新元素，這中間涉及兩個(gè)過程，首先就是找到數(shù)組下標(biāo) i 對(duì)應(yīng)的數(shù)據(jù)元素A，然后將新的數(shù)據(jù)元素B賦值給A即完成更新。

簡單舉例，代碼如下：

int[] array={1,2,3,4,5,6}; 
System.out.println(array[1]);  // 輸出的是2 
 
//更新數(shù)組下標(biāo)為 1 的數(shù)組元素 
array[1]=22; 
System.out.println(array[1]); // 輸出的是22   

3. 插入元素

相比讀取、更新操作，插入元素稍微復(fù)雜一些，分為以下兩種情況：

尾部插入：首先，我們看看尾部插入，這種情況很簡單，在數(shù)組的最后新增一個(gè)新的元素，此時(shí)對(duì)于原數(shù)組來說沒有任何影響，時(shí)間復(fù)雜度為0(1)。如下圖所示：

中間插入：如果在數(shù)組的中間位置插入元素的話，此時(shí)會(huì)對(duì)插入元素位置之后的元素產(chǎn)生影響，也就是這些數(shù)據(jù)需要向后依次挪動(dòng)一個(gè)位置。如下圖所示：

中間插入的代碼如下：

/** 
 *  插入元素 
 * @param index  待插入的位置 
 * @param element 待插入的元素 
*/ 
public void insert(int index,int element){ 
    if(index<0 || index>size){ 
       throw new IndexOutOfBoundsException("超過數(shù)組容量 ! 插入失??！"); 
     } 
    // 從左到右，將元素向右移動(dòng)一位 
    for (int i=size-1 ; i>index ; i--){ 
       array[i+1]=array[i]; 
    } 
    // 此時(shí)index這個(gè)位置已經(jīng)騰空了，可以放進(jìn)入element 
    array[index]=element; 
    //數(shù)組中元素個(gè)數(shù)+1 
    size++; 
} 

3.1 數(shù)組擴(kuò)容

因?yàn)閿?shù)組的長度在創(chuàng)建的時(shí)候已經(jīng)確定了，當(dāng)插入元素的時(shí)候如果數(shù)組已經(jīng)滿了，是沒辦法插入成功的。這個(gè)時(shí)候就要考慮數(shù)組擴(kuò)容的問題了，那么該如何實(shí)現(xiàn)擴(kuò)容呢?

其實(shí)我們可以這樣，比如此時(shí)的數(shù)組是A, A已經(jīng)滿了，我們?cè)賱?chuàng)建一個(gè)數(shù)組B且數(shù)組長度是A的2倍，然后我們將數(shù)組A的元素全部放到數(shù)組B中，這樣就完成了數(shù)組擴(kuò)容了。

數(shù)組擴(kuò)容的代碼如下:

/** 
 * 數(shù)組擴(kuò)容為原數(shù)組的二倍 
 */ 
public void resize(){ 
 int[] newArray=new int[array.length*2]; 
 System.arraycopy(array,0,newArray,0,array.length); 
 array=newArray; 

4. 刪除元素

刪除元素和插入元素類似，如果我們刪除第k個(gè)位置的數(shù)據(jù)，為了內(nèi)存的連續(xù)性，同樣會(huì)涉及數(shù)據(jù)的挪動(dòng)。如下圖所示：

刪除元素的代碼如下：

/** 
 * 根據(jù)數(shù)組下標(biāo)刪除元素 
 * 
 * @param index 數(shù)組下標(biāo) 
 * @return 
 */ 
public int delete(int index) { 
    if (index < 0 || index > size) { 
        throw new IndexOutOfBoundsException("已經(jīng)超過數(shù)組容量 ! 插入失??！"); 
    } 
    int deleteElement = array[index]; 
    // 從左到右，將元素向左移動(dòng)一位 
    for (int i = index; i < size - 1; i++) { 
        array[i] = array[i + 1]; 
    } 
    size--; 
    return deleteElement; 
} 

總結(jié)

數(shù)組是使用一塊連續(xù)的內(nèi)存空間，存儲(chǔ)相同類型的一組數(shù)據(jù)，其最大的優(yōu)點(diǎn)是數(shù)組支持隨機(jī)訪問，是因?yàn)閿?shù)組可以通過數(shù)組下標(biāo)(尋址公式)快速訪問對(duì)應(yīng)元素，時(shí)間復(fù)雜度為O(1)。

數(shù)組在刪除元素和插入元素這兩個(gè)操作比較低效，是因?yàn)閿?shù)組為了保持?jǐn)?shù)據(jù)的連續(xù)性，會(huì)涉及到數(shù)據(jù)的挪動(dòng)，平均時(shí)間復(fù)雜度為O(N)。