資料結構與算法之連結清單------數組與連結清單的對比

數組與連結清單的定義

數組：數組是一組具有相同類型和名稱的變量集合。這些變量稱為數組的元素。每個數組元素都有一個編号，這個編号叫做下标。我們可以通過下标來區分這些元素。數組元素個數。數組元素的個數也稱之為數組的長度。

連結清單：連結清單的特性是在中間位置增加删除元素都非常的快，不需要移動其它的元素。通常連結清單每個元素都有儲存指向下一個元素的指針。還要儲存上一個元素的指針。循環連結清單則把最後一個元素的指針指向第一個元素。

差別

從邏輯結構上看

數組必須事先定義一個固定大小的長度(元素個數),不能适應動态的增減情況。當資料增加時，可能會超出原先定義的個數，出現記憶體溢出。當資料減少時，又會造成記憶體浪費。數組中的插入和删除，需要移動其它資料項。

連結清單則能動态進行存儲配置設定。對于程式員友善快捷。可以動态的增加或删減。可以友善的插入或删除資料項而不移動其它的資料項

從記憶體存儲來看

（靜态）數組從棧中配置設定空間，對于程式員友善快捷自由度小。

而連結清單是從堆中配置設定空間，自由度大但是申請管理比較麻煩。

總結

引傳入連結表克服了數組的局限性，它允許動态的配置設定所需數量的記憶體。同時資訊的插入和删除操作對于數組的影響是局部的，進而使這些操作更容易實作了。在數組的前面插入一個新的元素，數組中的所有元素都需要移動，為新元素騰出空間。是以插入操作對于數組的影響數全局的，删除也是如此。

但是數組還是有些超過連結清單的優勢，即數組允許随機通路，如果需要直接通路元素，那麼數組是一個更好的選擇。對于二叉查找和大部分的排序算法。這都是更好的選擇。但如果經常通路的隻是某幾個元素，而且算法的核心不斷改變結構，那麼使用連結清單是一個更好的選擇。

使用數組的另一個優點是節約空間。在數組中用于存儲某項的單元隻要和該項的大小一樣即可。但在連結清單中，每個節點還需要至少包含一個引用域。對于一個大連結清單，需要相當數量的記憶體來存儲引用。

轉載于:https://my.oschina.net/mrminlingchao/blog/317850