數組： 一種非常基礎且重要的數據結構
本文轉載自微信公眾號「碼上Java」，作者碼上Java。轉載本文請聯系碼上Java公眾號。
前言
數組是一種非常基礎且重要的數據結構，很多復雜的數據結構都是基于數組實現的。深入理解數據的存儲原理和特點，有利于我們在實際開發工作中，充分發揮數據的優勢。
數據是什么
數組的定義：數組(Array)是一種線性表數據結構。它用一組連續的內存空間，存儲一組具有相同類型的數據。
在上面的定義中加黑的描述，我們可以發現數組的幾個特點，分別是：線性表、連續的內存空間、相同類型的數據。如下圖所示：
數組因具有連續的內存空間的特點，讓數據擁有非常高效率的“隨機訪問”，但也是因為要保持這個連續的內存空間，導致數組在刪除或插入操作的時非常低效。因為數組為了保持連續性，必然會涉及大量數據的搬移，這個是非常消耗時間的。
思考：這里你可能會有疑問：什么是連續的內存空間?
首先，我們來說說內存，內存是由一個個連續的內存單元組成的，每一個內存單元都有自己的地址。在這些內存單元中，有些被其他數據占用了，有些是空閑的。
然而數據中的每個元素，都存儲在小小的內存單元中，并且元素之間緊密排列，既不能打亂元素的存儲順序，也不能跳過某個存儲單元進行存儲。
數組的隨機訪問
數組的隨機訪問是有個尋址公式的，上問中我們提到過數組是用一組連續的內存空間存儲數據元素的，然而每個內存單元都有自己的地址(在計算機里面就是通過這個地址訪問數據的)，又加上每個內存單元的大小都是一樣的，這樣就很容易得到一個公式了，如下所示：
- a[i]_address=base_address+i*data_type_size
我們來簡單解釋一下上述公式，其中data_type_size表示數組中每個元素的大小、base_address表示內存塊的首地址、i 表示數組下標。
數組的基本操作
在開始之前我們先創建一個數組類，來模擬數組操作時候的相關操作。代碼如下:
- public class MyArray {
- private int[] array;
- // 數組大小
- private int size;
- public MyArray(int capacity) {
- this.size = 0;
- this.array = new int[capacity];
- }
- }
1. 讀取元素
我們知道數組在內存中是連續存儲的，所以根據上文的尋址公式可以知道，我們可以根據數組下標 i 快速定位到對應的元素。
簡單舉例，代碼如下：
- int[] array={1,2,3,4,5,6};
- System.out.println(array[1]); // 輸出的是2 因為數組的下標是從0開始的。
2. 更新元素
我們可以根據數組下標快速查找到對應元素。那么同樣道理，我們可以根據數組下標 i 快速更新元素，這中間涉及兩個過程，首先就是找到數組下標 i 對應的數據元素A，然后將新的數據元素B賦值給A即完成更新。
簡單舉例，代碼如下：
- int[] array={1,2,3,4,5,6};
- System.out.println(array[1]); // 輸出的是2
- //更新數組下標為 1 的數組元素
- array[1]=22;
- System.out.println(array[1]); // 輸出的是22
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++;
- }
3.1 數組擴容
因為數組的長度在創建的時候已經確定了，當插入元素的時候如果數組已經滿了，是沒辦法插入成功的。這個時候就要考慮數組擴容的問題了，那么該如何實現擴容呢?
其實我們可以這樣，比如此時的數組是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);
- array=newArray;
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;
- }
總結
數組是使用一塊連續的內存空間，存儲相同類型的一組數據，其最大的優點是數組支持隨機訪問，是因為數組可以通過數組下標(尋址公式)快速訪問對應元素，時間復雜度為O(1)。
數組在刪除元素和插入元素這兩個操作比較低效，是因為數組為了保持數據的連續性，會涉及到數據的挪動，平均時間復雜度為O(N)。
