為什麼數組比連結清單查詢速度更快？

這是一個大廠的interview題

自己回答的很菜

為什麼數組比連結清單查詢速度更快？

• 數組由于是緊湊連續存儲,可以随機通路，通過索引快速找到對應元素，而且相對節約存儲空間。但正因為連續存儲，記憶體空間必須一次性配置設定夠，是以說數組如果要擴容，需要重新配置設定一塊更大的空間，再把資料全部複制過去，時間複雜度 O(N)；而且你如果想在數組中間進行插入和删除，每次必須搬移後面的所有資料以保持連續，時間複雜度 O(N)。
• 連結清單因為元素不連續，而是靠指針指向下一個元素的位置，是以不存在數組的擴容問題；如果知道某一進制素的前驅和後驅，操作指針即可删除該元素或者插入新元素，時間複雜度O(1)。但是正因為存儲空間不連續，你無法根據一個索引算出對應元素的位址，是以不能随機通路；而且由于每個元素必須存儲指向前後元素位置的指針，會消耗相對更多的儲存空間。

另外值得驚醒的一句話是：

資料結構的存儲方式隻有兩種：數組（順序存儲）和連結清單（鍊式存儲）

這句話怎麼了解，不是還有散清單、棧、隊列、堆、樹、圖等等各種資料結構嗎？

• 我們分析問題，一定要有遞歸的思想，自頂向下，從抽象到具體。你上來就列出這麼多，那些都屬于「上層建築」，而數組和連結清單才是「結構基礎」。因為那些多樣化的資料結構，究其源頭，都是在連結清單或者數組上的特殊操作，API

  不同而已。

• 比如說「隊列」、「棧」這兩種資料結構既可以使用連結清單也可以使用數組實作。用數組實作，就要處理擴容縮容的問題；用連結清單實作，沒有這個問題，但需要更多的記憶體空間存儲節點指針。
• 「圖」的兩種表示方法，鄰接表就是連結清單，鄰接矩陣就是二維數組。鄰接矩陣判斷連通性迅速，并可以進行矩陣運算解決一些問題，但是如果圖比較稀疏的話很耗費空間。鄰接表比較節省空間，但是很多操作的效率上肯定比不過鄰接矩陣。

• 「散清單」就是通過散列函數把鍵映射到一個大數組裡。而且對于解決散列沖突的方法，拉鍊法需要連結清單特性，操作簡單，但需要額外的空間存儲指針；線性探查法就需要數組特性，以便連續尋址，不需要指針的存儲空間，但操作稍微複雜些。

  -「樹」，用數組實作就是「堆」，因為「堆」是一個完全二叉樹，用數組存儲不需要節點指針，操作也比較簡單；用連結清單實作就是很常見的那種「樹」，因為不一定是完全二叉樹，是以不适合用數組存儲。為此，在這種連結清單「樹」結構之上，又衍生出各種巧妙的設計，比如二叉搜尋樹、AVL樹、紅黑樹、區間樹、B 樹等等，以應對不同的問題。

• 了解 Redis 資料庫的朋友可能也知道，Redis 提供清單、字元串、集合等等幾種常用資料結構，但是對于每種資料結構，底層的存儲方式都至少有兩種，以便于根據存儲資料的實際情況使用合适的存儲方式。

資料結構種類很多，甚至你也可以發明自己的資料結構，但是底層存儲無非數組或者連結清單

轉載自：學習資料結構和算法的高效方法  ,為什麼數組比連結清單查詢速度更快？​​​​​​​