Linked List Explore Card 最後複習了單向與雙向鏈結陣列的差異，以及陣列與鏈結陣列的比較。

單向與雙向鏈結陣列

根據前面幾篇文章的內容，可以歸納出它們有以下三點相似之處：

1. 它們都沒辦法直接存取指定索引值的元素，必須要重頭開始遍歷整個鏈結陣列。
2. 它們不管是新增節點在開頭或是指定節點位置，都只需要花費O(1)的時間。
3. 它們刪除開頭節點只要花費O(1)的時間。

但它們對於刪除指定節點的方式有些許不同：

• 單向鏈結陣列沒辦法從尾端往前查詢節點，只能夠從頭開始遍歷搜尋，因此需要花費O(N)的時間，找到指定節點的前一個節點才能進行刪除操作。
• 雙向鏈結陣列對於刪除操作就比較簡單，因為使用prev可以取的前一個節點，能夠直接進行刪除操作，因此只需要O(1)的時間複雜度。

陣列與鏈結陣列

首先，比較陣列、單向鏈結陣列以及雙向鏈結陣列的時間複雜度：

這張圖表需要注意的地方是雙向鏈結陣列的部分，它有額外的變數指向尾端的節點，因此新增和刪除尾端的節點都是O(1)的時間複雜度，但如果沒有額外使用變數指向尾端的話，一樣需要從頭開始遍歷整個鏈結陣列，這樣就還是O(N)的時間複雜度。

LeetCode Problem

• 21. Merge Two Sorted Lists
• 2. Add Two Numbers
• 430. Flatten a Multilevel Doubly Linked List
• 138. Copy List with Random Pointer
• 61. Rotate List

小結

終於讀完Linked List 的Explore Card 了，沒想到鐵人賽已經過完一半，但Linked List 的LeetCode 題目還沒講完，裡面有三題Medium，看來需要多花一點時間思考如何解題了。

最後提醒如何選擇使用陣列及鏈結陣列：

• 如果需要經常根據索引值存取元素值，推薦使用陣列。
• 如果需要經常進行新增或刪除操作，推薦使用鏈結陣列。