1、聊一聊

本文主要跟大家分享一下數組和鏈表兩種內存組織類型的異同，幫助大家正確理解好這兩種數據結構并合理應用。

2、數組和鏈表的簡介

1. 數組

數組---一種有序、連續且有著相同元素的存儲結構。

特點：

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

2.  鏈表

鏈表---一種不一定有序、不一定連續、不一定相同元素的存儲結構。

特點：

•  元素不一定相同，只需要存在鏈接信息；
•  不需要內存連續；
•  非下標訪問，通過鏈接信息遍歷。

3、數組和鏈表的異同

1.  相同點

相同點比較少，兩者都是內存數據的一種組織方式，數組通過連續相同元素分配的特點來進行節點的訪問，而對于鏈表是通過鏈接關系(一般通過指針鏈接)來進行索引訪問。(下面所有的數組項和鏈表項都統一叫節點)

2.  不相同點

相同點相對比較少，不然其中一方必定替代另外一方，所以這里重點談談不同點:

1)動態擴容

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

如果分配的數組之前僅僅只有7個節點空間，當需要插入7節點的時候，需要把所有的內存copy到一個更大的內存空間，然后再把7插入。

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

2)更好的利用Cache

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

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

3)訪問節點方式

 這樣就很明顯了，數組通過下標可以直接訪問到對應的節點，而鏈表需要通過頭指針不斷的進行遍歷從而找到對應的節點。例如:我們想直接訪問數組的第三個節點，直接通過Array[2]即可，而對于鏈表則通過頭指針，不斷的找下一個節點最終找到第三個節點的位置，這樣鏈表的時間復雜度就比數組大。

4)節約內存

對于數組由于其固定的順序存儲格式特點所以直接可以通過下標訪問，然而對于鏈表的不連續性，其每個節點必須要存儲其前驅或者后繼的鏈接信息，這樣就需要使用額外的內存空間進行信息保存，當節點比較多時可是一筆不小的內存開支。

4、一個討論點分析

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

1.  情況1    

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

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

情況1總結：

• 對于該情況下數組和鏈表的復雜度相差不大，數組需要后移新插入點后的所有節點，然后再插入新節點，而對于鏈表需要首先遍歷找到對應的節點，然后進行插入。

2.  情況2    

上圖數組在數據1后面插入一個新的節點，首先數組需要遍歷知道數據1，然后移動3,5,6數據節點，并插入新節點。

上圖數組在數據1后面插入一個新的節點，首先鏈表需要遍歷知道數據1，然后直接插入新節點。

情況2總結：

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

4、最后小結

看完本文的小伙伴應該對數組和鏈表有了更加清晰的認識，其實這些對比對于以后大家進行一些代碼上的優化和設計是非常有幫助的，大家好好體會一下！