1、聊一聊

本文主要跟大家分享一下數(shù)組和鏈表兩種內(nèi)存組織類型的異同，幫助大家正確理解好這兩種數(shù)據(jù)結(jié)構(gòu)并合理應(yīng)用。

2、數(shù)組和鏈表的簡介

1. 數(shù)組

數(shù)組---一種有序、連續(xù)且有著相同元素的存儲結(jié)構(gòu)。

特點(diǎn)：

•  相同的元素類型；
•  依次連續(xù)順序存放；
•  通過下標(biāo)可以直接訪問。

2.  鏈表

鏈表---一種不一定有序、不一定連續(xù)、不一定相同元素的存儲結(jié)構(gòu)。

特點(diǎn)：

•  元素不一定相同，只需要存在鏈接信息；
•  不需要內(nèi)存連續(xù)；
•  非下標(biāo)訪問，通過鏈接信息遍歷。

3、數(shù)組和鏈表的異同

1.  相同點(diǎn)

相同點(diǎn)比較少，兩者都是內(nèi)存數(shù)據(jù)的一種組織方式，數(shù)組通過連續(xù)相同元素分配的特點(diǎn)來進(jìn)行節(jié)點(diǎn)的訪問，而對于鏈表是通過鏈接關(guān)系(一般通過指針鏈接)來進(jìn)行索引訪問。(下面所有的數(shù)組項和鏈表項都統(tǒng)一叫節(jié)點(diǎn))

2.  不相同點(diǎn)

相同點(diǎn)相對比較少，不然其中一方必定替代另外一方，所以這里重點(diǎn)談?wù)劜煌c(diǎn):

1)動態(tài)擴(kuò)容

通過前面兩者的特點(diǎn)我們知道，數(shù)組屬于連續(xù)分配，一般都在定義的時候分配給定的大小，而鏈表卻可以實(shí)現(xiàn)動態(tài)的節(jié)點(diǎn)插入和移除，這樣對于一些內(nèi)存利用空間多變的情況，使用鏈表會帶來更多的靈活度和內(nèi)存的利用率。如下圖所示:

如果分配的數(shù)組之前僅僅只有7個節(jié)點(diǎn)空間，當(dāng)需要插入7節(jié)點(diǎn)的時候，需要把所有的內(nèi)存copy到一個更大的內(nèi)存空間，然后再把7插入。

對于鏈表其實(shí)就不存在擴(kuò)大容量的問題，如果空間足夠且指針能夠索引到，便可以"無限"擴(kuò)充。

2)更好的利用Cache

在含有Cache的系統(tǒng)中，由于CPU的訪問速度相對普通內(nèi)存而言不在一個數(shù)量等級，為了不拖累CPU都會在其中間通過Cache來作為一個緩沖，可以大大提高CPU訪問主存的速度。

那么數(shù)組作為連續(xù)的內(nèi)存組織方式，更容易被同時加載到Cache中從而提高CPU對內(nèi)存數(shù)據(jù)的命中，并提高運(yùn)算速度和效率。

3)訪問節(jié)點(diǎn)方式

 這樣就很明顯了，數(shù)組通過下標(biāo)可以直接訪問到對應(yīng)的節(jié)點(diǎn)，而鏈表需要通過頭指針不斷的進(jìn)行遍歷從而找到對應(yīng)的節(jié)點(diǎn)。例如:我們想直接訪問數(shù)組的第三個節(jié)點(diǎn)，直接通過Array[2]即可，而對于鏈表則通過頭指針，不斷的找下一個節(jié)點(diǎn)最終找到第三個節(jié)點(diǎn)的位置，這樣鏈表的時間復(fù)雜度就比數(shù)組大。

4)節(jié)約內(nèi)存

對于數(shù)組由于其固定的順序存儲格式特點(diǎn)所以直接可以通過下標(biāo)訪問，然而對于鏈表的不連續(xù)性，其每個節(jié)點(diǎn)必須要存儲其前驅(qū)或者后繼的鏈接信息，這樣就需要使用額外的內(nèi)存空間進(jìn)行信息保存，當(dāng)節(jié)點(diǎn)比較多時可是一筆不小的內(nèi)存開支。

4、一個討論點(diǎn)分析

一問到數(shù)組和鏈表的應(yīng)用，大家一般都會想到一句話:"查詢修改用數(shù)組，插入刪除用鏈表"，那么bug菌就在這里跟大家分析分析這句話:

1.  情況1    

上圖數(shù)組在第四個元素后面插入一個節(jié)點(diǎn)，這樣需要把4,5,6節(jié)點(diǎn)依次向后面移動一個節(jié)點(diǎn)，然后把新的元素加入。

上圖鏈表中在4個位置插入一個新節(jié)點(diǎn)，首先需要通過遍歷知道第四個節(jié)點(diǎn)，然后直接通過改變指針進(jìn)行新節(jié)點(diǎn)的鏈表插入。

情況1總結(jié)：

• 對于該情況下數(shù)組和鏈表的復(fù)雜度相差不大，數(shù)組需要后移新插入點(diǎn)后的所有節(jié)點(diǎn)，然后再插入新節(jié)點(diǎn)，而對于鏈表需要首先遍歷找到對應(yīng)的節(jié)點(diǎn)，然后進(jìn)行插入。

2.  情況2    

上圖數(shù)組在數(shù)據(jù)1后面插入一個新的節(jié)點(diǎn)，首先數(shù)組需要遍歷知道數(shù)據(jù)1，然后移動3,5,6數(shù)據(jù)節(jié)點(diǎn)，并插入新節(jié)點(diǎn)。

上圖數(shù)組在數(shù)據(jù)1后面插入一個新的節(jié)點(diǎn)，首先鏈表需要遍歷知道數(shù)據(jù)1，然后直接插入新節(jié)點(diǎn)。

情況2總結(jié)：

•  所以對于該情況鏈表的復(fù)雜度比數(shù)組要低，所以具體情況具體分析，比如直接在頭結(jié)點(diǎn)插入新節(jié)點(diǎn)的情況，鏈表比數(shù)組更優(yōu)。僅僅只是查找和修改，其兩者相差不大，不過數(shù)組更加方便。

4、最后小結(jié)

看完本文的小伙伴應(yīng)該對數(shù)組和鏈表有了更加清晰的認(rèn)識，其實(shí)這些對比對于以后大家進(jìn)行一些代碼上的優(yōu)化和設(shè)計是非常有幫助的，大家好好體會一下！