一、聊一聊
本文主要跟大家分享一下陣列和鏈表兩種記憶體組織型別的異同，幫助大家正確理解好這兩種資料結構并合理應用，
二、陣列和鏈表的簡介
1. 陣列
陣列---一種有序、連續且有著相同元素的存盤結構，
特點：
|
? 相同的元素型別； ? 依次連續順序存放； ? 通過下標可以直接訪問， |
2. 鏈表
鏈表---一種不一定有序、不一定連續、不一定相同元素的存盤結構，
特點：
|
? 元素不一定相同，只需要存在鏈接資訊； ? 不需要記憶體連續； ? 非下標訪問，通過鏈接資訊遍歷， |
三、陣列和鏈表的異同
1. 相同點
相同點比較少，兩者都是記憶體資料的一種組織方式，陣列通過連續相同元素分配的特點來進行節點的訪問，而對于鏈表是通過鏈接關系(一般通過指標鏈接)來進行索引訪問，(下面所有的陣列項和鏈表項都統一叫節點)
2. 不相同點
相同點相對比較少，不然其中一方必定替代另外一方，所以這里重點談談不同點:
1) 動態擴容
通過前面兩者的特點我們知道，陣列屬于連續分配，一般都在定義的時候分配給定的大小，而鏈表卻可以實作動態的節點插入和移除，這樣對于一些記憶體利用空間多變的情況，使用鏈表會帶來更多的靈活度和記憶體的利用率，如下圖所示:
如果分配的陣列之前僅僅只有7個節點空間，當需要插入7節點的時候，需要把所有的記憶體copy到一個更大的記憶體空間，然后再把7插入，
對于鏈表其實就不存在擴大容量的問題，如果空間足夠且指標能夠索引到，便可以"無限"擴充，
2) 更好的利用Cache
在含有Cache的系統中，由于CPU的訪問速度相對普通記憶體而言不在一個數量等級，為了不拖累CPU都會在其中間通過Cache來作為一個緩沖，可以大大提高CPU訪問主存的速度，
那么陣列作為連續的記憶體組織方式，更容易被同時加載到Cache中從而提高CPU對記憶體資料的命中，并提高運算速度和效率，
3) 訪問節點方式
這樣就很明顯了，陣列通過下標可以直接訪問到對應的節點，而鏈表需要通過頭指標不斷的進行遍歷從而找到對應的節點，
例如:我們想直接訪問陣列的第三個節點，直接通過Array[2]即可，而對于鏈表則通過頭指標，不斷的找下一個節點最終找到第三個節點的位置，這樣鏈表的時間復雜度就比陣列大，
4) 節約記憶體
對于陣列由于其固定的順序存盤格式特點所以直接可以通過下標訪問，然而對于鏈表的不連續性，其每個節點必須要存盤其前驅或者后繼的鏈接資訊，這樣就需要使用額外的記憶體空間進行資訊保存，當節點比較多時可是一筆不小的記憶體開支，
四、一個討論點分析
一問到陣列和鏈表的應用，大家一般都會想到一句話:"查詢修改用陣列，插入洗掉用鏈表"，那么bug菌就在這里跟大家分析分析這句話:
1. 情況1
上圖陣列在第四個元素后面插入一個節點，這樣需要把4,5,6節點依次向后面移動一個節點，然后把新的元素加入，
上圖鏈表中在4個位置插入一個新節點，首先需要通過遍歷知道第四個節點，然后直接通過改變指標進行新節點的鏈表插入，
情況 1 總結：
對于該情況下陣列和鏈表的復雜度相差不大，陣列需要后移新插入點后的所有節點，然后再插入新節點，而對于鏈表需要首先遍歷找到對應的節點，然后進行插入，
2. 情況2
上圖陣列在資料1后面插入一個新的節點，首先陣列需要遍歷知道資料1，然后移動3,5,6資料節點，并插入新節點，
上圖陣列在資料1后面插入一個新的節點，首先鏈表需要遍歷知道資料1，然后直接插入新節點，
情況 2 總結：
所以對于該情況鏈表的復雜度比陣列要低，所以具體情況具體分析，比如直接在頭結點插入新節點的情況，鏈表比陣列更優，僅僅只是查找和修改，其兩者相差不大，不過陣列更加方便，
最后小結
看完本文的小伙伴應該對陣列和鏈表有了更加清晰的認識，其實這些對比對于以后大家進行一些代碼上的優化和設計是非常有幫助的，大家好好體會一下！
不管你是轉行也好，初學也罷，進階也可——【值得關注進入】的C/C++編程學習進階俱樂部
涉及到：C語言、C++、windows編程、網路編程、QT界面開發、Linux編程、游戲編程、黑客等等......
一個活躍、高格調、高層次的程式員編程學習殿堂；編程入門只是順帶，思維的提高才有價值！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/220339.html
標籤：C
上一篇：一口氣帶你讀懂80年IT發展史
下一篇：技術點13：Cookie