順序表與鏈表的比較 ?順序表與單鏈表的比較 ?存儲分配方式、時(shí)間性能、空間性能 ?順序表與鏈表的比較 ?空間比較、時(shí)間比較、語言比較 ? 存儲分配方式比較 ?順序表采用順序存儲結(jié)構(gòu)，即用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過存儲位置來實(shí)現(xiàn)。 ?單鏈表采用鏈接存儲結(jié)構(gòu)，即用一組任意的存儲單元存放線性表的元素。用指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系。 ? 時(shí)間性能比較 時(shí)間性能是指實(shí)現(xiàn)基于某種存儲結(jié)構(gòu)的基本操作（即算法）的時(shí)間復(fù)雜度。 按位查找： ?順序表的時(shí)間為Ｏ(1)，是隨機(jī)存取； ?單鏈表的時(shí)間為Ｏ(n)，是順序存取。 插入和刪除： ?順序表需移動表長一半的元素，時(shí)間為Ｏ(n)； ?單鏈表不需要移動元素，在給出某個(gè)合適位置的指針后，插入和刪除操作所需的時(shí)間僅為Ｏ(1)。 ? 空間性能比較 空間性能是指某種存儲結(jié)構(gòu)所占用的存儲空間的大小。 定義結(jié)點(diǎn)的存儲密度： 存儲密度＝數(shù)據(jù)域占用的存儲量/整個(gè)結(jié)點(diǎn)占用的存儲量 結(jié)點(diǎn)的存儲密度： ?順序表中每個(gè)結(jié)點(diǎn)的存儲密度為1（只存儲數(shù)據(jù)元素）， ?單鏈表的每個(gè)結(jié)點(diǎn)的存儲密度<1（包括數(shù)據(jù)域和指針域），有指針的結(jié)構(gòu)性開銷。 整體結(jié)構(gòu)： ?順序表需要預(yù)分配存儲空間，如果預(yù)分配得過大，造成浪費(fèi)，若估計(jì)得過小，又將發(fā)生上溢； ?單鏈表不需要預(yù)分配空間，只要有內(nèi)存空間可以分配，單鏈表中的元素個(gè)數(shù)就沒有限制。 ?

?空間比較：

?(1) 順序表空間靜態(tài)分配；鏈表空間動態(tài)分配

?(2)順序表的存儲密度 = 1；鏈表的存儲密度 < 1。

?時(shí)間比較： (1)順序表可隨機(jī)存取，也可順序存取；鏈表只能順序存取 (2)插入/刪除時(shí)，順序表平均移動一半左右元素；鏈表不需移動元素，只修改指針。若插入/刪除僅在表的兩端，宜采用帶尾指針的循環(huán)鏈表。 ?語言比較： 　順序表實(shí)現(xiàn)簡單：數(shù)組；動態(tài)鏈表：指針；靜態(tài)鏈表：數(shù)組

?

轉(zhuǎn)載于:https://www.cnblogs.com/wwj9413/archive/2011/10/15/2292815.html

總結(jié)

以上是生活随笔為你收集整理的顺序表与链表的比较的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。