建站
咨詢
售后
建站咨詢
新聞中心
1、聊一聊
本文主要跟大家分享一下數(shù)組和鏈表兩種內(nèi)存組織類型的異同，幫助大家正確理解好這兩種數(shù)據(jù)結(jié)構(gòu)并合理應(yīng)用。
2、數(shù)組和鏈表的簡介
1. 數(shù)組
數(shù)組---一種有序、連續(xù)且有著相同元素的存儲結(jié)構(gòu)。
特點：
- 相同的元素類型；
- 依次連續(xù)順序存放；
- 通過下標可以直接訪問。
2. 鏈表
鏈表---一種不一定有序、不一定連續(xù)、不一定相同元素的存儲結(jié)構(gòu)。
特點：
- 元素不一定相同，只需要存在鏈接信息；
- 不需要內(nèi)存連續(xù)；
- 非下標訪問，通過鏈接信息遍歷。
3、數(shù)組和鏈表的異同
1. 相同點
相同點比較少，兩者都是內(nèi)存數(shù)據(jù)的一種組織方式，數(shù)組通過連續(xù)相同元素分配的特點來進行節(jié)點的訪問，而對于鏈表是通過鏈接關(guān)系(一般通過指針鏈接)來進行索引訪問。(下面所有的數(shù)組項和鏈表項都統(tǒng)一叫節(jié)點)
2. 不相同點
相同點相對比較少，不然其中一方必定替代另外一方，所以這里重點談?wù)劜煌c:
1)動態(tài)擴容
通過前面兩者的特點我們知道，數(shù)組屬于連續(xù)分配，一般都在定義的時候分配給定的大小，而鏈表卻可以實現(xiàn)動態(tài)的節(jié)點插入和移除，這樣對于一些內(nèi)存利用空間多變的情況，使用鏈表會帶來更多的靈活度和內(nèi)存的利用率。如下圖所示:
如果分配的數(shù)組之前僅僅只有7個節(jié)點空間，當需要插入7節(jié)點的時候，需要把所有的內(nèi)存copy到一個更大的內(nèi)存空間，然后再把7插入。
對于鏈表其實就不存在擴大容量的問題，如果空間足夠且指針能夠索引到，便可以"無限"擴充。
2)更好的利用Cache
在含有Cache的系統(tǒng)中，由于CPU的訪問速度相對普通內(nèi)存而言不在一個數(shù)量等級，為了不拖累CPU都會在其中間通過Cache來作為一個緩沖，可以大大提高CPU訪問主存的速度。
那么數(shù)組作為連續(xù)的內(nèi)存組織方式，更容易被同時加載到Cache中從而提高CPU對內(nèi)存數(shù)據(jù)的命中，并提高運算速度和效率。
3)訪問節(jié)點方式
這樣就很明顯了，數(shù)組通過下標可以直接訪問到對應(yīng)的節(jié)點，而鏈表需要通過頭指針不斷的進行遍歷從而找到對應(yīng)的節(jié)點。例如:我們想直接訪問數(shù)組的第三個節(jié)點，直接通過Array[2]即可，而對于鏈表則通過頭指針，不斷的找下一個節(jié)點最終找到第三個節(jié)點的位置，這樣鏈表的時間復(fù)雜度就比數(shù)組大。
4)節(jié)約內(nèi)存
對于數(shù)組由于其固定的順序存儲格式特點所以直接可以通過下標訪問，然而對于鏈表的不連續(xù)性，其每個節(jié)點必須要存儲其前驅(qū)或者后繼的鏈接信息，這樣就需要使用額外的內(nèi)存空間進行信息保存，當節(jié)點比較多時可是一筆不小的內(nèi)存開支。
4、一個討論點分析
一問到數(shù)組和鏈表的應(yīng)用，大家一般都會想到一句話:"查詢修改用數(shù)組，插入刪除用鏈表"，那么bug菌就在這里跟大家分析分析這句話:
1. 情況1
上圖數(shù)組在第四個元素后面插入一個節(jié)點，這樣需要把4,5,6節(jié)點依次向后面移動一個節(jié)點，然后把新的元素加入。
上圖鏈表中在4個位置插入一個新節(jié)點，首先需要通過遍歷知道第四個節(jié)點，然后直接通過改變指針進行新節(jié)點的鏈表插入。
情況1總結(jié)：
- 對于該情況下數(shù)組和鏈表的復(fù)雜度相差不大，數(shù)組需要后移新插入點后的所有節(jié)點，然后再插入新節(jié)點，而對于鏈表需要首先遍歷找到對應(yīng)的節(jié)點，然后進行插入。
2. 情況2
上圖數(shù)組在數(shù)據(jù)1后面插入一個新的節(jié)點，首先數(shù)組需要遍歷知道數(shù)據(jù)1，然后移動3,5,6數(shù)據(jù)節(jié)點，并插入新節(jié)點。
上圖數(shù)組在數(shù)據(jù)1后面插入一個新的節(jié)點，首先鏈表需要遍歷知道數(shù)據(jù)1，然后直接插入新節(jié)點。
情況2總結(jié)：
- 所以對于該情況鏈表的復(fù)雜度比數(shù)組要低，所以具體情況具體分析，比如直接在頭結(jié)點插入新節(jié)點的情況，鏈表比數(shù)組更優(yōu)。僅僅只是查找和修改，其兩者相差不大，不過數(shù)組更加方便。
4、最后小結(jié)
看完本文的小伙伴應(yīng)該對數(shù)組和鏈表有了更加清晰的認識，其實這些對比對于以后大家進行一些代碼上的優(yōu)化和設(shè)計是非常有幫助的，大家好好體會一下！
文章標題：C語言有了"鏈表"還用"數(shù)組"干嘛?被問懵了......
標題URL：http://www.5511xx.com/article/dhhgpjp.html
