DOJO004
什麼是”鏈表 ( Linked List)”?
演算法
第一次聽到真的一頭霧水，不是本科系應該不會接觸到吧🥲
GPT 的解釋
鏈表（Linked List）是一種線性數據結構，由一系列節點（Node）組成，每個節點包含兩部分：數據（Data）和指向下一個節點的引用（或指針，Pointer）。鏈表的特點是節點之間不是連續存儲的，而是通過指針連接在一起。
鏈表的主要類型有：
- 單向鏈表（Singly Linked List）：每個節點只包含一個指向下一個節點的引用。
- 雙向鏈表（Doubly Linked List）：每個節點包含兩個引用，一個指向下一個節點，另一個指向前一個節點。
- 循環鏈表（Circular Linked List）：單向或雙向鏈表的變體，在這種鏈表中，最後一個節點指向頭節點，形成一個循環結構。
鏈表的優點：
- 動態大小：鏈表的長度可以隨著元素的增加或刪除動態改變。
- 插入和刪除操作較快：在鏈表的任意位置進行插入和刪除操作，只需要修改相鄰節點的指針，而不需要像數組那樣移動大量元素。
鏈表的缺點：
- 訪問速度較慢：需要從頭節點開始逐個遍歷，才能找到某個特定的節點。
- 額外的空間開銷：每個節點都需要額外存儲指針，會佔用更多的內存。
一個簡單的單向鏈表的示例：
Head -> [Data | Next] -> [Data | Next] -> [Data | Next] -> Null
在這個示例中，"Head" 是鏈表的頭節點，每個節點包含數據和一個指向下一個節點的引用，最後一個節點的引用為空（Null），表示鏈表的結尾。
雙向列表的示例：
Head <-> [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] <-> Null
雙向鏈表中的每個節點都包含三部分：數據（Data）、指向下一個節點的引用（Next）和指向前一個節點的引用（Prev）。
循環列表的示例：
// 單向循環鏈表的結構示例 Head -> [Data | Next] -> [Data | Next] -> [Data | Next] --+ ^ | |---------------------------------------------------+ // 雙向循環鏈表的結構示例 Head <-> [Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next] ^ | |--------------------------------------------------------------------------+
循環鏈表中的每個節點都包含數據和指向下一個節點的引用，在單向或雙向鏈表的基礎上，最後一個節點指向頭節點，形成一個循環。
關於 Linked List 與 Array 的比較，可以看這邊文章，寫得非常詳細!
happy coding!
