【洪小漢】評論

接著我們就要去分析陣列和鏈結串列的時間複雜度，做優缺點的分析:Array優點:存取只需要 O(1) 時間對 Array 的資料做存取。比 Linked list 為節省記憶體空間，因為 linked list 需要多一個指標 pointer 來記錄下一個節點的記憶體位置。缺點:新增/刪除資料比較麻煩，若要在第一個位置新增資料，就需要把矩陣中所有元素往後移動，並且是O(N)的時間複雜度。同理，若要刪除第一個位置的資料，也需要 O(N) 的時間複雜度把矩陣中剩餘的元素往前移動。若時常在新增資料，要時常調整陣列的大小，會花費 O(N) 的時間在搬動資料(把資料從舊的陣列移動到新的陣列)。適用時機：快速存取資料時已知資料的數量，如此便不用經常改變陣列大小要求記憶體空間的使用越少越好。Linked list優點：新增/刪除資料比 Array 簡單，只要對要新增刪除的相關節點們調整指標即可，不需要像 Array 搬動其餘元素。linked list 的資料數量能動態的向記憶體要空間或釋放空間，不像 Array 會有 "重新定義陣列大小" 的問題。缺點:因為 linked list 不能直接透過索引值找到某節點(ex: 像陣列可以透過 array[index] 找到要的元素)，若要找到特定節點，需要從頭開始找起，搜尋的時間複雜度為 O(N)。需要額外的記憶體空間來儲存指標。適用時機：無法預期資料數量或頻繁變動資料數量時。需要頻繁地新增/刪除資料時。不需要快速查詢資料。以上內容就是陣列和鏈結串列的比較，明天我們將來學習堆疊!https://ithelp.ithome.com.tw/articles/10217537