數(shù)據(jù)結(jié)構(gòu)與算法——數(shù)組

DangoSky 發(fā)布于2019-08-16 15:45 / 3008人閱讀

摘要：概述數(shù)組是一種很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，幾乎絕大多數(shù)編程語言都會支持?jǐn)?shù)組這種數(shù)據(jù)結(jié)構(gòu)。數(shù)組是一種線性結(jié)構(gòu)，使用一組連續(xù)的內(nèi)存空間，來存儲相同類型的數(shù)據(jù)。

1. 概述

數(shù)組（Array）是一種很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，幾乎絕大多數(shù)編程語言都會支持?jǐn)?shù)組這種數(shù)據(jù)結(jié)構(gòu)。數(shù)組是一種線性結(jié)構(gòu)，使用一組連續(xù)的內(nèi)存空間，來存儲相同類型的數(shù)據(jù)。

所謂線性結(jié)構(gòu)，就是指數(shù)據(jù)是前后排列的，只有前后兩個方向，除了數(shù)組，其他的比如鏈表、棧、隊(duì)列都是線性結(jié)構(gòu)。

因?yàn)閿?shù)組是使用連續(xù)的內(nèi)存空間來存儲數(shù)據(jù)的，所以數(shù)組的最大的特點(diǎn)就是支持根據(jù)下標(biāo)隨機(jī)訪問數(shù)據(jù)，這是數(shù)組最大的優(yōu)勢。但是，有利就有弊，雖然數(shù)組高效的支持下標(biāo)訪問，只不過在插入和刪除數(shù)據(jù)的時候就比較低效了，為了保證內(nèi)存的連續(xù)性，必須要進(jìn)行數(shù)據(jù)搬移。

2. 插入數(shù)據(jù)

先來看看插入操作，假如有一個數(shù)組 [3, 4, 6, 8, 7, 2, 5]，第一種情況是插入的元素位于數(shù)組的最后一個位置，那么不用進(jìn)行數(shù)據(jù)搬移，時間復(fù)雜度為 O(1) ，如果插入的位置是第一個，那么必須移動整個數(shù)組，時間復(fù)雜度為 O(n) 。

這里有另外一個處理思路：如果數(shù)組中存儲的數(shù)據(jù)不在乎彼此順序的話，那么插入數(shù)據(jù)的時候，我們可以直接將插入位置的元素放到數(shù)組最后一位，騰出位置給新的元素。就像下圖這樣：

3. 刪除數(shù)據(jù)

再來看看刪除操作，還是上面的數(shù)組 [3, 4, 6, 8, 7, 2, 5]，如果刪除的是最后一個元素，那么不需要進(jìn)行數(shù)據(jù)搬移，如果刪除的是第一個元素，那么數(shù)組每一個元素都會向前移動一位。

只不過，在某些場景下，如果不是特別追求數(shù)據(jù)的連續(xù)性，那么我們可以采用另一種思路來處理刪除操作。例如數(shù)組的大小為 10 ，現(xiàn)在存儲了 7 個元素，分別是 [3, 4, 6, 8, 7, 2, 5]，如果我們要刪除 3 4 6 這三個元素，我們先將其標(biāo)記為刪除，等到數(shù)組空間不夠的時候，在集中性的進(jìn)行數(shù)據(jù)搬移，這樣就大大減少了數(shù)據(jù)搬移的次數(shù)！

是不是非常高效呢？

4. Java 容器

在 Java 語言中，提供了一個可以支持動態(tài)擴(kuò)容的數(shù)組容器：ArrayList，如果你熟悉 Java 語言的話，幾乎每天都會和這個容器打交道，它封裝了一些數(shù)組的操作，并且在數(shù)組空間不夠的時候，自動擴(kuò)容為原來的 1.5 倍。

只不過，在使用 ArrayList 的時候，要是能夠指定大小，最好指定，這樣會減少申請內(nèi)存空間和數(shù)據(jù)搬移的操作。

5. 代碼示例

下面是簡單的支持動態(tài)擴(kuò)容的數(shù)組實(shí)現(xiàn)：

/*
 * 泛型動態(tài)數(shù)組
 */
public class GenericArray {

    private T[] data;
    private int count;//數(shù)組中存儲的個數(shù)
    
    public GenericArray(int capacity) {
        this.data = (T[]) new Object[capacity];
        this.count = 0;
    }

    public GenericArray() {
        this(16);
    }
    
    //返回?cái)?shù)組中元素的個數(shù)
    public int getSize() {
        return this.count;
    }
    
    //返回?cái)?shù)組容量
    public int getCapacity() {
        return this.data.length;
    }

    //設(shè)置某個位置的數(shù)據(jù)
    public void set(int index, T value) {
        if (count == data.length) {
            //擴(kuò)容
            resize(data.length * 2);
        }
        checkIndex(index);
        
        if (index == count) {
            data[count ++] = value;
            return;
        }
        //常規(guī)刪除
        for (int i = count; i < index; i --) 
            data[i] = data[i - 1];
        data[index] = value;
        count ++;
    }
    
    //在數(shù)組末尾插入數(shù)據(jù)
    public void insert(T value) {
        set(count, value);
    }
    
    //刪除數(shù)據(jù) 
    public T remove(int index) {
        if(index == count) throw new IllegalArgumentException("Index Illegal!");
        checkIndex(index);
        
        T result = data[index];
        
        for (int i = index; i < count - 1; i ++) 
            data[i] = data[i + 1];
        count --;
        
        //縮容
        if (count == data.length / 2) {
            resize(data.length / 2);
        }
        return result;
    }
    
    //檢查下標(biāo)的方法
    public void checkIndex(int index) {
        if(index < 0 || index > count) throw new IllegalArgumentException("Index Illegal!");
    }
    
    //重新設(shè)置數(shù)組的容量, 對應(yīng)的操作是擴(kuò)容和縮容
    private void resize(int capacity) {
        T[] temp = (T[]) new Object[capacity];
        for (int i = 0; i < count; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }
}

是不是很簡單呢？后面接著講數(shù)據(jù)結(jié)構(gòu)與算法的知識！