11、數組和鏈表的優缺點

　　數組，在內存上給出了連續的空間。鏈表，內存地址上可以是不連續的，每個鏈表的節點包括原來的內存和下一個節點的信息(單向的一個，雙向鏈表的話，會有兩個)。

　　數組優于鏈表的:

　　A. 內存空間占用的少，因為鏈表節點會附加上一塊或兩塊下一個節點的信息。

　　但是數組在建立時就固定了。所以也有可能會因為建立的數組過大或不足引起內存上的問題。

　　B. 數組內的數據可隨機訪問，但鏈表不具備隨機訪問性。這個很容易理解，數組在內存里是連續的空間，比如如果一個數組地址從100到200，且每個元素占用兩個字節，那么100-200之間的任何一個偶數都是數組元素的地址，可以直接訪問。

　　鏈表在內存地址可能是分散的。所以必須通過上一節點中的信息找能找到下一個節點。

　　C. 查找速度上。這個也是因為內存地址的連續性的問題，不羅索了。

　　鏈表優于數組的:

　　A. 插入與刪除的操作。如果數組的中間插入一個元素，那么這個元素后的所有元素的內存地址都要往后移動。刪除的話同理。只有對數據的最后一個元素進行插入刪除操作時，才比較快。鏈表只需要更改有必要更改的節點內的節點信息就夠了。并不需要更改節點的內存地址。

　　B. 內存地址的利用率方面。不管你內存里還有多少空間，如果沒辦法一次性給出數組所需的要空間，那就會提示內存不足，磁盤空間整理的原因之一在這里。而鏈表可以是分散的空間地址。

　　C. 鏈表的擴展性比數組好。因為一個數組建立后所占用的空間大小就是固定的，如果滿了就沒法擴展，只能新建一個更大空間的數組;而鏈表不是固定的，可以很方便的擴展。

　　相關推薦：

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)