前言
線性表是數(shù)據(jù)結(jié)構(gòu)中最基本的一種數(shù)據(jù)存儲方式渴庆，深入了解線性表的特性不僅有助于更好地理解復(fù)雜數(shù)據(jù)結(jié)構(gòu)（例如棧铃芦、隊列等），還能給程序員的日常工作所需的內(nèi)功大法打下一個基礎(chǔ)襟雷。本文會從“定義”刃滓、“模型類比”、“性能評價”等多個維度對“順序存儲結(jié)構(gòu)”耸弄、“鏈?zhǔn)酱鎯Y(jié)構(gòu)”等線性表結(jié)構(gòu)進(jìn)行循序漸進(jìn)的闡述咧虎，如有錯誤或描述不清的地方， 歡迎指導(dǎo)计呈。
什么是線性表老客？
線性表即零個或多個有限元素的有限序列僚饭。
- 線性表首先強調(diào)的是“有限”，然后是“序列性”胧砰，即每個元素從前后關(guān)系上來看都有一一對應(yīng)的關(guān)系。
- 十二星座是不是線性表呢苇瓣？答案是YES尉间，因為從“有限”和“序列性”上來考慮，十二星座的結(jié)構(gòu)是符合要求的击罪。
- 公司的組織架構(gòu)是不是呢哲嘲？首先它滿足了“有限”特性，但由于整體結(jié)構(gòu)呈“樹狀”媳禁，而非線性眠副，所以它并不是線性表。
線性表結(jié)構(gòu)??????
非線性表結(jié)構(gòu)??????
線性表的順序存儲結(jié)構(gòu)
定義
順序存儲結(jié)構(gòu)的順序二字竣稽，是針對物理結(jié)構(gòu)而言的囱怕。使用順序存儲結(jié)構(gòu)時, 系統(tǒng)會按照給定的長度在內(nèi)存中開辟一段固定長度且連續(xù)的空間，也因此順序存儲結(jié)構(gòu)存在內(nèi)存溢出的問題毫别。模型類比
電影院的座位就是一個線性表的順序存儲結(jié)構(gòu)娃弓，在建造的時候甲方就是根據(jù)給定的設(shè)計建造出固定數(shù)量的座位。這些座位不僅是有限的岛宦，而且是按照固定順序排序編號的台丛。如果看電影的人數(shù)超出了總座位數(shù)量，則“內(nèi)存溢出”砾肺。-
插入+刪除+查詢性能
- 由于內(nèi)存地址是連續(xù)的挽霉，在進(jìn)行查詢操作時，只需要根據(jù)地址就能馬上找到對應(yīng)元素变汪，因此查詢的時間復(fù)雜度未O(1)侠坎。
-
在進(jìn)行插入和刪除操作時，每操作一個元素疫衩，其他相關(guān)元素都要移動一下硅蹦，給即將加入的元素“讓位”， 或者“補上”被刪除的元素的位置闷煤。這個過程很好理解童芹，舉個例子，電影院有100個座位鲤拿，目前有99個觀眾坐在1號到99號的座位上假褪，突然來了一個傻逼觀眾，一定要坐到1號的座位上近顷，此時這99個觀眾都需要向后挪一個座位生音，才能給這個傻逼讓出1號座位宁否，而這個過程的時間負(fù)責(zé)度為O(n)。刪除的操作也是類似缀遍，如下圖所示慕匠。
存儲結(jié)構(gòu)的刪除操作
線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)
鏈?zhǔn)酱鎯Y(jié)構(gòu)和順序剛好相反，它沒有固定長度域醇，而且物理空間也是不連續(xù)的台谊，因此除非系統(tǒng)的所有內(nèi)存空間都被用完了， 否則不存在內(nèi)存溢出問題譬挚。
-
單鏈表定義
單鏈表由有限結(jié)點組成锅铅，每個結(jié)點由數(shù)據(jù)域和指針域組成， 數(shù)據(jù)域用來保存數(shù)據(jù)减宣，指針域用來指向下一個元素盐须。
單鏈表 模型類比
很多探寶電影都會有這么一個橋段，主角出現(xiàn)在地點一漆腌，得到一些好處贼邓，然后又得到提示前往下一個地點，到了下一個地點又得到一些好處屉凯，然后又得到提示前往再下一個地點立帖，以此類推直到找到最后的大秘寶，而這個過程中所經(jīng)過的每一個地點在物理空間上都是不連續(xù)的悠砚。以單鏈表來類比晓勇，每個地點都是一個結(jié)點，主角們得到的好處即數(shù)據(jù)灌旧，得到的提示即指針域绑咱，想要獲取下一個結(jié)點的數(shù)據(jù)， 只能通過前一個指針域獲取枢泰。-
插入+刪除+查詢性能
- 通過前文的類比解釋可以得出一個結(jié)果描融，使用單鏈表時，要進(jìn)行查詢操作衡蚂，只能一個結(jié)點一個結(jié)點地找下去窿克，直到找出自己要查詢的數(shù)據(jù)為止，因此單鏈表的查詢操作的時間復(fù)雜度為O(n)毛甲。
- 而對于插入操作和刪除操作年叮，只需要在要插入的位置，重新指定前后結(jié)點的指針域的指向即可玻募，因此時間復(fù)雜度為O(1)只损，具體操作如下圖所示。
結(jié)語
對比順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)后的數(shù)據(jù)操作性能后， 我們會發(fā)現(xiàn)兩者在時間復(fù)雜度上的表現(xiàn)是剛好相反的跃惫，由此也可以得出一個簡單的結(jié)論叮叹，對于長度不變且不需要頻繁進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)，我們應(yīng)該使用順序存儲結(jié)構(gòu)爆存，而對于長度不確定且需要頻繁進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)蛉顽，我們應(yīng)該優(yōu)先使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。兩者各有利弊终蒂，而且有不同的適用場景蜂林，應(yīng)該根據(jù)需求選擇性地使用。
