順序表 鏈表

?存儲分配方式、時間性能、空間性能

?順序表與鏈表的比較

?空間比較、時間比較巫玻、語言比較

存儲分配方式比較

?順序表采用順序存儲結構，即用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素祠汇，數(shù)據(jù)元素之間的邏輯關系通過存儲位置來實現(xiàn)仍秤。

?單鏈表采用鏈接存儲結構，即用一組任意的存儲單元存放線性表的元素可很。用指針來反映數(shù)據(jù)元素之間的邏輯關系诗力。

時間性能比較

時間性能是指實現(xiàn)基于某種存儲結構的基本操作（即算法）的時間復雜度。

按位查找：

?順序表的時間為Ｏ(1)我抠，是隨機存任尽；

?單鏈表的時間為Ｏ(n)菜拓，是順序存取瓣窄。

插入和刪除：

?順序表需移動表長一半的元素，時間為Ｏ(n)纳鼎；

?單鏈表不需要移動元素俺夕，在給出某個合適位置的指針后，插入和刪除操作所需的時間僅為Ｏ(1)贱鄙。

空間性能比較

空間性能是指某種存儲結構所占用的存儲空間的大小劝贸。

定義結點的存儲密度：

存儲密度＝數(shù)據(jù)域占用的存儲量/整個結點占用的存儲量

結點的存儲密度：

?順序表中每個結點的存儲密度為1（只存儲數(shù)據(jù)元素），

?單鏈表的每個結點的存儲密度<1（包括數(shù)據(jù)域和指針域）逗宁，有指針的結構性開銷悬荣。

整體結構：

?順序表需要預分配存儲空間，如果預分配得過大疙剑，造成浪費氯迂，若估計得過小，又將發(fā)生上溢言缤；

?單鏈表不需要預分配空間嚼蚀，只要有內(nèi)存空間可以分配，單鏈表中的元素個數(shù)就沒有限制管挟。

?空間比較：

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

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

?時間比較：

(1)順序表可隨機存取导帝，也可順序存仁匚健；鏈表只能順序存取

(2)插入/刪除時您单，順序表平均移動一半左右元素斋荞；鏈表不需移動元素，只修改指針虐秦。若插入/刪除僅在表的兩端平酿，宜采用帶尾指針的循環(huán)鏈表。

?語言比較：

順序表實現(xiàn)簡單：數(shù)組悦陋；動態(tài)鏈表：指針蜈彼；靜態(tài)鏈表：數(shù)組

最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個濱河市俺驶，隨后出現(xiàn)的幾起案子幸逆，更是在濱河造成了極大的恐慌，老刑警劉巖暮现，帶你破解...
    沈念sama閱讀 217,826評論 6贊 506
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件还绘，死亡現(xiàn)場離奇詭異，居然都是意外死亡送矩，警方通過查閱死者的電腦和手機蚕甥，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,968評論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來栋荸，“玉大人菇怀，你說我怎么就攤上這事∩慰椋” “怎么了爱沟？”我有些...
    開封第一講書人閱讀 164,234評論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長匆背。 經(jīng)常有香客問我呼伸，道長，這世上最難降的妖魔是什么钝尸？ 我笑而不...
    開封第一講書人閱讀 58,562評論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任括享，我火速辦了婚禮，結果婚禮上珍促，老公的妹妹穿的比我還像新娘铃辖。我一直安慰自己，他們只是感情好猪叙，可當我...
    茶點故事閱讀 67,611評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布娇斩。 她就那樣靜靜地躺著仁卷，像睡著了一般。 火紅的嫁衣襯著肌膚如雪犬第。 梳的紋絲不亂的頭發(fā)上锦积，一...
    開封第一講書人閱讀 51,482評論 1贊 302
  • 城市分裂傳說
    那天，我揣著相機與錄音歉嗓，去河邊找鬼丰介。 笑死，一個胖子當著我的面吹牛遥椿，可吹牛的內(nèi)容都是我干的基矮。 我是一名探鬼主播淆储，決...
    沈念sama閱讀 40,271評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼冠场，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了本砰？” 一聲冷哼從身側響起碴裙，我...
    開封第一講書人閱讀 39,166評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎点额，沒想到半個月后舔株，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,608評論 1贊 314
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡还棱，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,814評論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年载慈，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片珍手。...
    茶點故事閱讀 39,926評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡办铡，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出琳要，到底是詐尸還是另有隱情寡具，我是刑警寧澤，帶...
    沈念sama閱讀 35,644評論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布稚补，位于F島的核電站童叠，受9級特大地震影響，放射性物質發(fā)生泄漏课幕。R本人自食惡果不足惜厦坛，卻給世界環(huán)境...
    茶點故事閱讀 41,249評論 3贊 329
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望乍惊。 院中可真熱鬧杜秸，春花似錦、人聲如沸污桦。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,866評論 0贊 22
  • 一樁弒父案匙监，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至小作，卻和暖如春亭姥，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背顾稀。 一陣腳步聲響...
    開封第一講書人閱讀 32,991評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工达罗， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人静秆。 一個月前我還...
    沈念sama閱讀 48,063評論 3贊 370
  • 代替公主和親
    正文 我出身青樓粮揉，卻偏偏與公主長得像，于是被迫代替她去往敵國和親抚笔。 傳聞我的和親對象是個殘疾皇子扶认，可洞房花燭夜當晚...
    茶點故事閱讀 44,871評論 2贊 354

推薦閱讀更多精彩內(nèi)容