**連結清單與數組的優缺點**

原文連結：https://blog.csdn.net/Mormont/article/details/53439772

1.數組：

數組是将元素在記憶體中連續存放，由于每個元素占用記憶體相同，可以通過下标迅速通路數組中任何元素。但是如果要

在數組中增加一個元素，需要移動大量元素，在記憶體中空出一個元素的空間，然後将要增加的元素放在其中。同樣的

道理，如果想删除一個元素，同樣需要移動大量元素去填掉被移動的元素。如果應用需要快速通路資料，很少插入和

删除元素，就應該用數組。

2.連結清單：

連結清單中的元素在記憶體中不是順序存儲的，而是通過存在元素中的指針聯系到一起，每個結點包括兩個部分：一個是存

儲資料元素 的資料域，另一個是存儲下一個結點位址的 指針。如果要通路連結清單中一個元素，需要從第一個元素始，

一直找到需要的元素位置。但是增加和删除一個元素對于連結清單資料結構就非常簡單了，隻要修改元素中的指針就可以

了。如果應用需要經常插入和删除元素你就需要用連結清單。

3.差別：

（1）存儲位置上：

數組邏輯上相鄰的元素在實體存儲位置上也相鄰，而連結清單不一定；

（2）存儲空間上：

連結清單存放的記憶體空間可以是連續的，也可以是不連續的，數組則是連續的一段記憶體空間。一般情況下存放相同多的數

據數組占用較小的記憶體，而連結清單還需要存放其前驅和後繼的空間。

（3）長度的可變性：

連結清單的長度是按實際需要可以伸縮的，而數組的長度是在定義時要給定的，如果存放的資料個數超過了數組的初始大

小，則會出現溢出現象。

（4）按序号查找時，數組可以随機通路，時間複雜度為O(1)，而連結清單不支援随機通路，平均需要O(n)；

（5）按值查找時，若數組無序，數組和連結清單時間複雜度均為O(1)，但是當數組有序時，可以采用折半查找将時間複

雜度降為O(logn)；

（6）插入和删除時，數組平均需要移動n/2個元素，而連結清單隻需修改指針即可；

（7）空間配置設定方面：

數組在靜态存儲配置設定情形下，存儲元素數量受限制，動态存儲配置設定情形下，雖然存儲空間可以擴充，但需要移動大量

元素，導緻操作效率降低，而且如果記憶體中沒有更大塊連續存儲空間将導緻配置設定失敗； 即數組從棧中配置設定空間,，對

于程式員友善快速,但自由度小。

連結清單存儲的節點空間隻在需要的時候申請配置設定，隻要記憶體中有空間就可以配置設定，操作比較靈活高效；即連結清單從堆中分

配空間, 自由度大但申請管理比較麻煩。