概述

數(shù)組　

????是將元素在內(nèi)存中連續(xù)存放，由于每個元素占用內(nèi)存相同，可以通過下標迅速訪問數(shù)組中任何元素。但是如果要在數(shù)組中增加一個元素，需要移動大量元素，在內(nèi)存中空出一個元素的空間，然后將要增加的元素放在其中。同樣的道理，如果想刪除一個元素，同樣需要移動大量元素去填掉被移動的元素。如果應用需要快速訪問數(shù)據(jù)，很少插入和刪除元素，就應該用數(shù)組。

鏈表　

????中的元素在內(nèi)存中不是順序存儲的，而是通過存在元素中的指針聯(lián)系到一起，每個結點包括兩個部分：一個是存儲 數(shù)據(jù)元素 的　數(shù)據(jù)域，另一個是存儲下一個結點地址的 指針。如果要訪問鏈表中一個元素，需要從第一個元素開始，一直找到需要的元素位置。但是增加和刪除一個元素對于鏈表數(shù)據(jù)結構就非常簡單了，只要修改元素中的指針就可以了。如果應用需要經(jīng)常插入和刪除元素你就需要用鏈表。

內(nèi)存存儲區(qū)別

數(shù)組從棧中分配空間, 對于程序員方便快速,但自由度小。

鏈表從堆中分配空間, 自由度大但申請管理比較麻煩。

總結

1、存取方式上，數(shù)組可以順序存取或者隨機存取，而鏈表只能順序存取；

2、存儲位置上，數(shù)組邏輯上相鄰的元素在物理存儲位置上也相鄰，而鏈表不一定；

3、存儲空間上，鏈表由于帶有指針域，存儲密度不如數(shù)組大；

4、按序號查找時，數(shù)組可以隨機訪問，時間復雜度為O(1)，而鏈表不支持隨機訪問，平均需要O(n)；

5、按值查找時，若數(shù)組無序，數(shù)組和鏈表時間復雜度均為O(1)，但是當數(shù)組有序時，可以采用折半查找將時間復雜度降為O(logn)；

6、插入和刪除時，數(shù)組平均需要移動n/2個元素，而鏈表只需修改指針即可；

7、空間分配方面：

數(shù)組在靜態(tài)存儲分配情形下，存儲元素數(shù)量受限制，動態(tài)存儲分配情形下，雖然存儲空間可以擴充，但需要移動大量元素，導致操作效率降低，而且如果內(nèi)存中沒有更大塊連續(xù)存儲空間將導致分配失敗；

鏈表存儲的節(jié)點空間只在需要的時候申請分配，只要內(nèi)存中有空間就可以分配，操作比較靈活高效；