數(shù)組特性：

1.線性表（包括數(shù)組、鏈表、隊(duì)列和棧等）
2.連續(xù)內(nèi)存空間和相同類(lèi)型數(shù)據(jù)。

基于特性2：連續(xù)的內(nèi)存空間和相同類(lèi)型數(shù)據(jù)：

1.讓數(shù)組具有隨機(jī)訪問(wèn)特性。
2.為保證連續(xù)性，插入和刪除數(shù)據(jù)可能會(huì)做大量數(shù)據(jù)搬移工作。

理解：隨機(jī)訪問(wèn)特性（根據(jù)下標(biāo)進(jìn)行訪問(wèn)）

1.基于公式:a[i]_address=base_address + i*data_type_size。所以時(shí)間復(fù)雜度為O(1)。
2.注意：查找某個(gè)元素的時(shí)間復(fù)雜度不是O(1),對(duì)于排好序的數(shù)組二分查找（折半查找）時(shí)間復(fù)雜度也是O(logn)。

理解：插入操作（注意思考分配內(nèi)存不足的問(wèn)題）

1.尾部插入時(shí)間復(fù)雜度是O(1)（最好情況時(shí)間復(fù)雜度）。
2.頭部插入時(shí)間復(fù)雜度為O(n)（最壞情況時(shí)間復(fù)雜度）。
3.平均時(shí)間復(fù)雜度（1+2+3+...+n)/n=O(n)。
4.優(yōu)化方式：
  不需要保證穩(wěn)定性的情況下將插入位置的數(shù)據(jù)放在最后，然后再插入數(shù)據(jù)。
  對(duì)于連續(xù)插入可以一次性插入。

理解：刪除操作

1.尾部刪除時(shí)間復(fù)雜度O(1)（最好）。
2.頭部刪除時(shí)間復(fù)雜度O(n)(最壞)。
3.優(yōu)化方式：
   特殊場(chǎng)景下，不一定追求數(shù)據(jù)連續(xù)性，可以將多次刪除集中為一次操作，減少數(shù)據(jù)搬移。類(lèi)比java中JVM標(biāo)記-清除算法的思想。

警惕數(shù)組越界

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}
    這段c代碼中，由于人為失誤：導(dǎo)致數(shù)組越界，數(shù)組越界造成了無(wú)限循環(huán)。對(duì)于不同編譯器，在分配內(nèi)存時(shí)，會(huì)按照內(nèi)存地址遞增或遞減的方式進(jìn)行分配。上面按照遞減方式進(jìn)行會(huì)出現(xiàn)無(wú)限循環(huán)。

    在 C 語(yǔ)言中，只要不是訪問(wèn)受限的內(nèi)存，所有的內(nèi)存空間都是可以自由訪問(wèn)的。根據(jù)我們前面講的數(shù)組尋址公式，a[3] 也會(huì)被定位到某塊不屬于數(shù)組的內(nèi)存地址上，而這個(gè)地址正好是存儲(chǔ)變量 i 的內(nèi)存地址，那么 a[3]=0 就相當(dāng)于 i=0，所以就會(huì)導(dǎo)致代碼無(wú)限循環(huán)。

說(shuō)說(shuō)數(shù)組和鏈表

1.數(shù)組對(duì)內(nèi)存要求較高，需要連續(xù)。
2.鏈表需要額外的空間存指定地址。
3.數(shù)組由于連續(xù)內(nèi)存空間和相同類(lèi)型數(shù)據(jù)具有隨機(jī)訪問(wèn)特性（n(1)）。
4.鏈表更適合插入刪除。在無(wú)法保證連續(xù)的大的內(nèi)存空間的時(shí)候適合使用。性能更好。

Java中數(shù)組和容器ArrayList各自?xún)?yōu)缺點(diǎn)對(duì)比

1.ArrayList封裝了數(shù)組操作中的細(xì)節(jié)，如：在插入刪除過(guò)程中數(shù)據(jù)的搬移。
2.ArrayList支持動(dòng)態(tài)擴(kuò)容。這些細(xì)節(jié)不需要我們實(shí)現(xiàn)。注意：擴(kuò)容涉及內(nèi)存申請(qǐng)和數(shù)據(jù)搬移，比較耗時(shí)，建議創(chuàng)建ArrayList的時(shí)候就指定數(shù)據(jù)大小。

3.數(shù)組中如果需要更大的空間，將原來(lái)的數(shù)據(jù)復(fù)制進(jìn)去，然后再將新的數(shù)據(jù)插入進(jìn)行。這些需要我們來(lái)做。

4.ArrayList無(wú)法存儲(chǔ)基本類(lèi)型，需要基礎(chǔ)類(lèi)型的包裝類(lèi)，拆箱裝箱需要一定性能消耗。希望使用基本數(shù)據(jù)類(lèi)型就用數(shù)組。
5.針對(duì)二維數(shù)組或多維數(shù)組，Object[][]array比ArrayList<ArrayList>array更直觀。

總結(jié)：對(duì)于業(yè)務(wù)開(kāi)發(fā)用容器省時(shí)省力，損失性能不大，對(duì)底層開(kāi)發(fā)對(duì)性能要求高的數(shù)組優(yōu)于容器。

數(shù)組相關(guān)code:https://github.com/wangzheng0822/algo/tree/master/java/05_array

數(shù)據(jù)結(jié)構(gòu)和算法，你如果不接觸可能以后都不會(huì)接觸，但是你接觸了，你就會(huì)感覺(jué)到它的好。
數(shù)據(jù)結(jié)構(gòu)和算法建議大家可以看看這個(gè)專(zhuān)欄老師寫(xiě)的很好，很感謝他：http://gk.link/a/103WJ