基本介紹
定義
數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)说搅，它用一組連續(xù)的內(nèi)存空間炸枣，來(lái)存儲(chǔ)一組具有相同類型的數(shù)據(jù)。
特性
從定義可以看出弄唧，數(shù)組的特性主要有兩個(gè)：
線性表：
線性表的定義-百度百科：
線性表是最基本适肠、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)候引。線性表是數(shù)據(jù)結(jié)構(gòu)的一種侯养，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。
從這句話我們可以知道：
a. 線性表是一個(gè)序列澄干。
b. 線性表是有限的逛揩。
c. 線性表的數(shù)據(jù)元素具有相同的特性。
常見的線性表：數(shù)組麸俘，鏈表辩稽，隊(duì)列，棧等从媚。連續(xù)的內(nèi)存空間逞泄， 相同類型的數(shù)據(jù)：我們平時(shí)使用最多的元素隨機(jī)訪問(wèn)，就是歸功于數(shù)組的這個(gè)特性。
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
-
支持隨機(jī)訪問(wèn)： 如上文所說(shuō)喷众，數(shù)組存于連續(xù)的地址空間各谚，并且存儲(chǔ)的是相同類型的數(shù)據(jù)，這使得數(shù)組可以通過(guò)下標(biāo)與數(shù)據(jù)類型的大小直接定位到數(shù)據(jù)位置到千。假設(shè)數(shù)組a的數(shù)據(jù)類型大小為size昌渤，那么可以得到第i 個(gè)元素的起始地址為：
a[i]_addr = base_addr + i * size
缺點(diǎn)
-
插入效率低
因?yàn)閿?shù)組要保證插入后數(shù)據(jù)的連續(xù)性，需要將插入位置后面的數(shù)據(jù)依次向后進(jìn)行移動(dòng)憔四，所以插入的效率很低愈涩。插入時(shí)最好的情況是在數(shù)組末尾插入，時(shí)間復(fù)雜度為O(1)加矛；最壞的情況是在數(shù)組起始位置插入，時(shí)間復(fù)雜度為O(n)煤篙；插入的平均時(shí)間復(fù)雜度為 (1+2+...+n)/n = O(n)斟览。
數(shù)組插入數(shù)據(jù)示例圖
優(yōu)化方法：如果數(shù)組內(nèi)元素不要求有序時(shí)，可以將原數(shù)組中第k個(gè)數(shù)據(jù)插入到數(shù)組末尾辑奈，然后將想要插入的數(shù)據(jù)插入到第k個(gè)位置即可苛茂。如上圖示例，可以將元素b插入到數(shù)組末尾鸠窗，再將f插入到b原來(lái)的位置妓羊。
-
刪除效率低
也是因?yàn)橐ＷC刪除后數(shù)據(jù)的連續(xù)性，需要將刪除位置后面的元素依次向前進(jìn)行移動(dòng)稍计，所以刪除的時(shí)間復(fù)雜度和插入一樣躁绸。即最好的情況是刪除末尾數(shù)據(jù)，時(shí)間復(fù)雜度為O(1)臣嚣；最壞的情況是刪除起始位置數(shù)據(jù)净刮，時(shí)間復(fù)雜度為O(n)；刪除的平均時(shí)間復(fù)雜度為O(n)硅则。
數(shù)組刪除數(shù)據(jù)示例圖
優(yōu)化方法：在允許數(shù)組內(nèi)存在無(wú)用數(shù)據(jù)的前提下淹父，需要?jiǎng)h除多個(gè)數(shù)據(jù)時(shí)可以采用標(biāo)記刪除法，即先不進(jìn)行實(shí)際刪除操作怎虫，而是先將所有需要?jiǎng)h除的數(shù)據(jù)標(biāo)記為被刪除狀態(tài)暑认，最后再進(jìn)行一次刪除操作清除掉所有被標(biāo)記的元素。
上面的優(yōu)化思路可以參考jvm的垃圾收集算法：jvm的垃圾回收算法中最基礎(chǔ)的收集算法是’標(biāo)記-清除‘算法大审。顧名思義蘸际，標(biāo)記清除算法分為’標(biāo)記‘和’清除‘兩個(gè)階段：首先標(biāo)記出所有需要回收的對(duì)象，在標(biāo)記完成后統(tǒng)一回收所有被標(biāo)記的對(duì)象饥努，參考下圖：
注意點(diǎn)
- 嚴(yán)格上來(lái)說(shuō)捡鱼，數(shù)組不是隨機(jī)查找的時(shí)間復(fù)雜度為O(1)，而是隨機(jī)訪問(wèn)的時(shí)間復(fù)雜度為O(1)。
- 使用數(shù)組進(jìn)行隨機(jī)訪問(wèn)時(shí)驾诈，一定要對(duì)數(shù)組越界訪問(wèn)時(shí)刻保持警惕缠诅，不然可能會(huì)有意想不到的后果。
參考資料
最近在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法備戰(zhàn)下一家公司的面試乍迄，做了一些總結(jié)并查閱了一些參考資料：
- 極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法專欄
- 百度百科
- 深入理解java虛擬機(jī)
我想說(shuō)
第一次寫技術(shù)文章管引，主要目的還是鍛煉一下自己的寫作與總結(jié)能力，希望可以借此機(jī)會(huì)激勵(lì)下自己闯两，多讀讀書褥伴，少玩點(diǎn)游戲 (?????)
大家有什么意見歡迎指出，我會(huì)虛心接受的漾狼。???
