一道考頻較高的面試題：數組和連結清單的差別

數組和連結清單雖然看似很基礎，但卻也經常被面試官問到，是以我們還是需要熟練掌握的。

差別1：記憶體上是否連續

• 數組在記憶體上是連續的
• 連結清單在記憶體上不是連續的,連結清單是通過指針指向下一個元素。

差別2：存放位置不同

• 數組存放在棧中
• 連結清單存放在堆中

差別3：查詢時間複雜度不同

• 數組查詢時間複雜度是O(1)
• 連結清單查詢時間複雜度是O(N)

差別4：插入或删除的時間複雜度不同

• 數組的時間複雜度是O(N)
• 連結清單的時間複雜度是O(1)

差別5：記憶體配置設定方式不同

• 數組是靜态配置設定記憶體
• 連結清單是動态配置設定記憶體