1、聊一聊

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

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

1. 數(shù)組

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

特點(diǎn)：

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

2.  鏈表

鏈表---一種不一定有序、不一定連續(xù)、不一定相同元素的存儲(chǔ)結(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)的訪問，而對(duì)于鏈表是通過鏈接關(guān)系(一般通過指針鏈接)來進(jìn)行索引訪問。(下面所有的數(shù)組項(xiàng)和鏈表項(xiàng)都統(tǒng)一叫節(jié)點(diǎn))

2.  不相同點(diǎn)

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

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

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

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

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

2)更好的利用Cache

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

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

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

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

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

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

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

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

1.  情況1    

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

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

情況1總結(jié)：

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

2.  情況2    

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

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

情況2總結(jié)：

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

4、最后小結(jié)

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