在一般的數(shù)據(jù)結(jié)構(gòu)教科書中镜悉，很少把數(shù)組單獨(dú)列一個(gè)章節(jié)來介紹，一般都是跟著鏈表一起順道介紹下禽绪，可能很多同學(xué)用了高級(jí)語(yǔ)言后蓖救，基本很少直接在代碼中使用數(shù)組了，所以對(duì)數(shù)據(jù)結(jié)構(gòu)中非常重要數(shù)組數(shù)據(jù)結(jié)構(gòu)知之甚少丐一。
數(shù)組的特點(diǎn)主要是線性的藻糖，并且數(shù)組中所有數(shù)據(jù)在內(nèi)存中占用的是連續(xù)的內(nèi)存空間和相同的數(shù)據(jù)類型。正是因?yàn)橛辛诉B續(xù)的存儲(chǔ)空間和同一數(shù)據(jù)類型的限制库车，這就讓數(shù)組可以很方便的做到通過數(shù)組下標(biāo)進(jìn)行數(shù)據(jù)隨機(jī)讀巨柒，并且時(shí)間復(fù)雜度是O(1)。但是同樣有這樣強(qiáng)大的優(yōu)點(diǎn)必然有缺點(diǎn)柠衍，數(shù)組的缺點(diǎn)就是在對(duì)數(shù)組進(jìn)行插入和刪除操作的時(shí)候洋满，為了保證數(shù)組中數(shù)據(jù)存儲(chǔ)的連續(xù)性，就需要對(duì)數(shù)據(jù)進(jìn)行遷移珍坊，如果是插入數(shù)據(jù)牺勾，那就要在插入位置將數(shù)據(jù)都后移；如果是刪除數(shù)據(jù)阵漏，那就要在刪除節(jié)點(diǎn)位置將后面的數(shù)據(jù)都前移驻民。因?yàn)椴迦牒蛣h除的最好和最壞時(shí)間復(fù)雜度分別是O(1)和O(n)翻具，那么根據(jù)平均復(fù)雜度算下來就是O(n)，可以說性能是比較差的回还。
數(shù)組的基本操作太簡(jiǎn)單了裆泳，這里就不介紹了，下面說下為什么數(shù)組的下標(biāo)隨機(jī)讀的時(shí)間復(fù)雜度只有O(1)柠硕，因?yàn)閿?shù)組有數(shù)據(jù)連續(xù)存儲(chǔ)和數(shù)組內(nèi)數(shù)據(jù)類型一致的特點(diǎn)工禾，這就讓計(jì)算機(jī)去根據(jù)下標(biāo)查找數(shù)據(jù)的內(nèi)存地址會(huì)非常方便，下面舉個(gè)例子：
int nums[] = {1,2,3,4};
對(duì)于這個(gè)數(shù)組蝗柔，計(jì)算機(jī)如果要讀取下標(biāo)為2的數(shù)值3怎么辦闻葵？首先獲取到nums數(shù)組的內(nèi)存地址，假設(shè)是0x00001癣丧，這里假設(shè)int數(shù)據(jù)類型占用4位槽畔，那么3這個(gè)數(shù)字保存在0x00009,這個(gè)地址很好算出來，因?yàn)槭沁B續(xù)存儲(chǔ)的坎缭，所以 下標(biāo)位i的目標(biāo)地址＝數(shù)組地址 ＋ 數(shù)據(jù)類型大芯固怠＊i签钩。
數(shù)組數(shù)據(jù)地址計(jì)算的公示也解釋了為什么數(shù)組下標(biāo)都是從0開始計(jì)數(shù)而不是從1開始掏呼，因?yàn)槿绻麖?開始，公示就會(huì)變成下標(biāo)位i的目標(biāo)地址＝數(shù)組地址 ＋ 數(shù)據(jù)類型大星﹂荨＊（i－1）憎夷，那么計(jì)算機(jī)就會(huì)多一次運(yùn)算，所以為了節(jié)約計(jì)算資源昧旨，設(shè)計(jì)成了下標(biāo)從0開始拾给。
下面再介紹下數(shù)組在哪些地方被用到了，我們?nèi)粘９ぷ髦杏玫淖疃嗟腁rrayList兔沃，在ArrayList底層就是通過數(shù)組來實(shí)現(xiàn)的蒋得，但是jdk將ArrayList底層數(shù)組的遷移操作都封裝了，并且在ArrayList底層還支持動(dòng)態(tài)擴(kuò)容乒疏，看了源碼就會(huì)知道所謂的動(dòng)態(tài)擴(kuò)容其實(shí)就是在原數(shù)組已經(jīng)存滿的情況下额衙，再申請(qǐng)1.5倍空間的新數(shù)組，將原數(shù)組數(shù)據(jù)都遷移到新數(shù)組中怕吴，一旦遇到需要擴(kuò)容性能就會(huì)下降很厲害窍侧，所以這就是為什么很多tips要求我們使用ArrayList的時(shí)候一定要根據(jù)預(yù)計(jì)數(shù)據(jù)量初始化大小，因?yàn)閖dk中ArrayList的默認(rèn)初始化空間很小转绷，如果不指定就會(huì)導(dǎo)致頻繁的擴(kuò)容伟件，進(jìn)行數(shù)據(jù)遷移。
也有同學(xué)會(huì)問既然已經(jīng)有了ArrayList那是不是可以完全拋棄數(shù)組了议经？當(dāng)然不是斧账。要知道ArrayList是無法保存基礎(chǔ)數(shù)據(jù)類型的谴返，像int、long這些基礎(chǔ)類型都要封裝位Integer咧织、Long類才行亏镰，而開箱和閉箱會(huì)導(dǎo)致性能損耗，所以對(duì)于使用基礎(chǔ)類型可以考慮使用數(shù)組拯爽。
其實(shí)對(duì)于數(shù)組這種數(shù)據(jù)結(jié)構(gòu)我們只要知道索抓，它是線性的，是連續(xù)存儲(chǔ)毯炮、同樣類型的集合逼肯，并且數(shù)組的隨機(jī)讀時(shí)間復(fù)雜度是O(1),插入和刪除時(shí)間復(fù)雜度是O(n)就可以了。在日常編程定義數(shù)據(jù)的時(shí)候考慮下這些特性就能知道使用數(shù)組在這些場(chǎng)景的性能如何了桃煎。
